Jacob's recent post on Lemmings clone Pingus reminded me of a similar game (similar in the penguin content anyway) which is also great fun to play and can give you that nostalgic feeling.
It is basically a Super Mario clone, called SuperTux. Unsurprisingly, instead of the moustached man, you control everyone's favourite operating system mascot, Tux.
There are currently two different versions of the game you can download - the stable, but older 0.1.3 and the newer, but as yet unstable 0.3.0 release. They are both great fun to play, and I tried the newer release briefly. Admittedly, I didn't have the time to get very far through the levels, but it seemed pretty well polished to me.
SuperTux is a very well done game and while it might not impress that much graphically, you really can't beat it for pure entertainment value.
SuperTux is free, open source and is available for Windows, Linux and Mac OS X. You can get it from the downloads page (it's probably best to search your package manager application for supertux if you are on Linux though).