Good point…I think I was trying to say “unknown” rather than “underrated”. But indeed it should hopefully become more known soon. Also good call on WADF, that’s a great puzzle-platformer.
Can you save frequently in Cave Story?
Fairly frequently. You can save whenever you’re at a save point, of which there are typically several in each area.
I wanna be the guy! I Wanna Be the Guy - Wikipedia
Heh. Not looking for massively difficult games. 
Dunno how good your PC is, but I enjoyed the heck out of Trine when I played it recently. It’s very clever and very pretty, and not at all much like most of the other games described in this thread, but definitely a platformer and puzzly.
Plus, hey, free demo.
Well, here is what we have played and our general opinion:
Every 2D Mario platformer(except the Gameboy ones): We liked them, especially Super Mario Bros. 3 and New Super Mario(DS)
Cave Story: Brilliant
Yoshi Island 1 and 2: Brilliant
Mega Man 1(NES): Dull
Mega Man X: Dull - We quit after about 4 stages.
Currently playing Donkey Kong Country 1: Nice, a bit easy, but cool.
Anyone have further recommendations? We are totally open for new games.
Oh, we will eventually try Plok. It does look cool. 
You could try Spelunky. An Indiana Jones inspired platformer with randomly generated levels. Get through the sixteen levels and escape with the treasure. It’s very… intricate is perhaps a good word. There are a lot of elements interacting with eachother, making for very varied and lastingly enjoyable gameplay. Why, I can think of at least four separate ways to make use of a damsel in distress.
Wonder Boy III: The Dragon’s Trap (Sega Master System)
May as well play the best Master System game, and one of the all time great platformers. Awesome music too.
Trine on PC is a fun co-op platformer with low enough system requirements that you could probably run it on most systems.
I really want to try it, but I can never get it to run on my PC, even the demo. I have a laptop, so perhaps that is the problem.
I actually had some problems getting the Trine demo to run before I upgraded my PC too; It was theoretically playable, but stuttery as heck. I really wouldn’t call it it a game with “low system requirements”, particular when you’re talking about platformers, most of which have REALLY LOW system requirements.
I try starting the game and it does nothing. It isn’t even running in the background.
My wife and I just started playing Wario Land 4 on the Gameboy Advance.
Weird game…and it has songs with singing, pretty cool for the GBA.
Are they other Wario Lands on the GB any good?
Yep, I already stated I was playing 1.
We finished it and will go back to that series when done with Wario Land 4.
I know this is a pretty specific question for a game, but I’m getting no response on the Gamefaqs message board for Wario Land 4. Anyone know the answer to my question?
It is:
Do you need all 4 diamond pieces on each level? If so, why?
I’m referring to the little triangles you get from the chests(they are purple and fill in a diamond shape when all are collected).
If you can help, thanks.
Another vote for the Megaman series, and I’ll throw in Solomon’s Key for a decent puzzler. (both NES)
How’d you play Braid if you don’t have a 360? Hm. Well, if you get access to a 360 again, you might want to try out Splosion Man, a rather wacky platformer that includes the wonderful donut song.
Originally on the Nintendo 64, but also available on Xbox Live Arcade now, is Banjo-Kazooie and the sequel, Banjo-Tooie. They’re 3D platformers rather than sidescrollers.
Since you liked Braid, I’ll also suggest The Misadventures of P.B. Winterbottom. Like Braid, you solve puzzles (in this case, stealing pies) by creating clones of yourself that are stuck in time, repeating their actions on a loop. The game has a great soundtrack and “silent film” look and feel to it.
It was released for the Xbox 360, the PC, MAC, and the PS3.
I played it on the PC, by the way.