Prehistorik Man (not to be confused with the game of the same name on the SNES, which is the sequel) was a platform game for the Game Boy, made by Titus Interactive. This game is actually a port of Prehistorik 2, which was made for MS-DOS and Amstrad CPC. Even with the major cuts out from the original PC game, Prehistorik Man seems to still be a rather faithful port, and pulled off some very interesting technical feats for the Game Boy.
CasualPokePlayer and WarHippy complete the game in record time.
See this run played back on the Game Boy Player (using Game Boy Interface) here.