Seconded Toejam & Earl and Cave Story.
I already played Cave Story. Thanks, though.
And Toejam & Earl isn’t a platformer (well, the first one wasn’t. Awesome game though).
I’m going to re-recommend Within a Deep Forest. It’s a puzzle-platformer, and it’s free. Cool atmosphere and graphics. http://nifflas.ni2.se/?page=Within+a+Deep+Forest
Well, two months and I think this isn’t a zombie(I think). It’s an ongoing thread for me, as my wife and I are greatly enjoying platformers and are looking for more.
Well, we more or less drained the nintendo and super nintendo and are trying some genesis games.
We just played Sonic 1.
Good Lord! The game is so fast and enemies/obstacles jump out from nowhere! We can barely keep up!
We liked it, but are on to Sonic 2 now. Hoping the series improves.
What other Genesis platformers should we try? Or any other good Nintendo or PC ones?
By the way, Plok was impossible. We gave up on that one(snes).
How about VVVVVV, a game about reversing (your own personal) gravity? There’s a demo in the link.
That’s the name of the game, man! 
I think there’s a jump in enjoyability from Sonic 1 to 2, because you get the spin-dash move in 2, and the levels are just more memorable. 2, 3, and 3 + Knuckles are all gold as far as I’m concerned.
Two people recommended Within A Deep Forest - I’m going to add that I’ve found two other games from the same developer, Knytt and Knytt Stories, to be pretty excellent. They are a little less puzzle-oriented than Within A Deep Forest, and a bit more about exploration.
By the way, my wife and I really enjoyed WarioWorld 2, 3, and 4.
Great puzzler platformers.