What, no mention of
Cave Story yet? Japanese freeware, but the site I linked to has a translation patch. It's another game with clear Metroid influence. Has a bundle of secrets too.
Also, I had
Supaplex when I was young, it was indeed quite fun and evil. You were allowed to skip three levels if you were stuck, too. Then when you were stuck after that you could go back and finish those and get your skips back.
As far as other games... I dunno.
Flipull is a pretty decent NES puzzle game that I remember. Only played it because my friend had a "Super 700-in-ONE" pirate cart.
I'd also like to say
The Neverhood. A great graphic adventure for the PC, if a bit short once you know what you're doing. I have a torrent running for the CD image, but I'm not sure if it's kosher to link to it. The game is abandonware, but the version available on the underdogs is crappy compared to the one I made.
Maybe I'll post more later if I think of anything else.