PC only. I know; that sucks.
Recently, I’ve played:
VVVVVV - Very cool game and I highly recommend it.
Braid - One of my all time favorite games.
Super Meat Boy - Fun, but nearly impossible at times. Still trying to beat it, actually.
I wish Limbo was out for PC, 'cause I’ve heard great things. I don’t want something impossible like “I wanna be the guy”, but I don’t mind a good challenge.
Any games I should get? What have I missed?
I’ve also played and loved Cave Story.
Forgot to mention it. 
Spelunky is pretty awesome. It’s very hard, but in a different way from Super Meat Boy. It’s more about thinking quickly than reacting quickly.
Randomly generated levels, though? Sounds weird.
I’d also be interested in any DS ones, too. I have played:
New Super Mario Bros DS
Super Princess Peach
Yoshi Island 2(AMAZING GAME)
Wario: Master of Disguise
Trine is a pretty neat little puzzle/platform type game. You control one of three characters (you can quickly switch between them at any time) and use their special abilities to advance through the level. The Knight can break through some doors and lift heavy objects. The wizard can levitate objects and create boxes and planks out of thin air. The Rogue has a grapple and a bow that can shoot regular or flaming arrows. So you might switch to the knight, pick up a boulder and throw it at a wooden barrier to break it, then switch to the wizard, make a couple boxes and stack them to climb on. Climb up and use the Rogue’s fire arrows to light a torch, then her grapple to swing across a chasm.
The combat is pretty easy for the most part, it’s getting though the natural obstacles in the level that’s a bit tricky. The Rogue’s grapple and the Wizard’s floating platforms take some dexterity to navigate but it’s not hair pulling difficult. The game is a lot of fun to play, the level design is pretty neat, the graphics are bright and colorful. Sound is pretty good and the music is ok.
I’d highly recommend it for all ages (I think younger players could probably get through most of it with minimal help, and there’s no bad language or sexual situations)
You could try the Robot wants… series. The games are all pretty good and have that 16-bit console platformer feel to them.
I can highly recommend Niffla’s Knytt series (and Within a Deep Forest) as well. Beautiful ,simple platformers.
NETA: I’ve heard good things about La-Mulana as well, but I have never been able to get it to work on my linux machine. It’s a classic metroidvania as far as I can tell.
Aquaria is a very pretty game, quite different, but I don’t know how replayable you’ll find it.
Somewhere between Braid and Limbo lies The Misadventures of P.B. Winterbottom. It has a black-and-white, old-timey movie feel to it, and it includes time manipulation puzzles similar to Braid. I’ve only played it on Xbox, but their site says it’s available on Steam.
I second Trine too. It has fantastic music, animation and environmental art. Trine 2 is coming out soon, rejoice!
Trine is extremely fun for co-op. Bring over a controller to your friend’s place, boot Trine, and you’ll have a hell of a time. It is possible to play with three players, but from what I gather in reviews, the game becomes too hard this way.
Trine is my favorite platformer of recent times - but I don’t have a ton to compare it to, not being a huge platformer fan. But it’s beautiful (easily the best looking platformer game I’ve ever seen), the puzzles are enough to be engaging without being super hard, and it’s just fun.
Trine looks awesome, but it also looks like it takes a powerhouse computer to run it.
I only have a decent laptop. 
Uh, not by any sane definition of “powerhouse”. Certainly, top end gaming rigs laugh at Trine’s system requirements and send them home to mommy - and that was when the game came out.
OTOH, I find people’s standards for “a decent laptop” tend to mean “It boots up in under tend minutes and I can browse the web” and that will certainly cause issues with Trine, but…well, here’re the sysreqs, right off their webpage:
Minimum PC system requirements
Processor: 2.0 GHz CPU
Operating System: Windows XP, Windows Vista or Windows 7
System Memory: 512 MB (XP), 1 GB (Vista)
Hard-Disk Space: 1 GB
Sound Card: (not required)
Video Card: Radeon X800 or GeForce 6800 or better
Other: -
Recommended PC system requirements
Processor: Dual-Core CPU or better
Operating System: Windows XP, Windows Vista or Windows 7
System Memory: 2 GB
Hard-Disk Space: 1 GB
Sound Card: DirectX compatible soundcard
Video Card: Radeon HD 3800 series or GeForce 8800 series or better
Other: gamepad(s) for co-op play
All that said, Platformers are basically the FPS of the Indie scene - everyone and their brother is making the darn things. Though I guess that’s an unfair comparison, since a lot of the indie platformers actually have original ideas. 
It’s this I don’t know much about:
Video Card: Radeon X800 or GeForce 6800 or better
Mine is just a laptop “on the board” kind of video card. It’s not too special.
I have a Dell Lattitude d620:
http://www.marketzoneng.com/mz_admin/upload/products/dell_latitude_d6201.jpg
I added 4 gig of memory to it(but it’s windows xp, so it only recognizes 3.2).
Anyway, any shot of Trine running on that bad boy? 
Well, you could always download the demo and try it? Historically Intel Onboard laptop graphics chips are pretty crummy for anything more advanced than showing your desktop, but if you got a Dell with the Nvidia option, things look better.
But mostly. Demo. Try it.
I can’t get either Trine or Professor Winterbottom to do anything other than immediately close when I try to start them.
Tried updating your graphics drivers?
They are updated. It’s because of the Dell Lattitude. It sucks for games, I guess.
I played Braid and Tales of Monkey Island on if flawlessly, but I have no idea why both of these games crash.
They just disappear and never open.