Add me to the list of people who told you to play Psychonauts: excellent characters, awesome and creative abilities, colourful and visionary places.
I played it with a controller, but for precise movements I used my keyboard: maybe it was not that hard for me as I'm used to play games without a controller, but I still advise you to try.

I read you disliked Sonic, but have you tried Sonic 3 & Knuckles? 12 brilliant levels and 3 characters with different abilites, so lots of replaying value - and the music is cool, too.

Really short, but nice, is a Cave Story clone (muuuch smaller) called Akuji the demon; it's also free!

I cannot avoid to mention old Apogee platforms, that made me *love* the genre: (in random order) , [url=http://www.gog.com/game/secret_agent]Secret Agent, Hocus Pocus (I loved this one, mainly for background music!), Cosmo's Cosmic Adventure, Crystal Caves, Monster Bash, the first Duke Nukem games, and, the last but probably the best, the whole Commander Keen series - the fourth chapter was shareware and I don't know how long I played it in frustration, as I didn't know where to buy the other parts!
If you want a short play, you can try one of these!

I had a long fascination for the (kinda horrible) ; of course another classic is [url=http://homeoftheunderdogs.net/game.php?id=4491] Jazz Jackrabbit and its sequels; the lately promo'd is nice and the underrated (in my opinion), but not so easy [url=http://it.wikipedia.org/wiki/Titus_The_Fox:_To_Marrakech_and_Back]Titus the Fox is cool, too!

For more modern graphics, you can try Heart of Darkness: it's parent to Oddworld: Abe's Odissey and it's frustrating! XD

Also some Disney platforms belong to the "gem" category: Aladdin, the Lion King and Maui Mallard in Cold Shadow (then try to forget its music...).

I restricted to PC games, but some of the console platforms are extremely good; the Donkey Kongs you quoted bring back awesome memories and I can't count how long I spent searching gems in Crash Bandicoot 3.

Sonic the Hedgehog
Sonic 3 & Knuckles
Earthworm Jim
Earthworm Jim 2
Super Mario Bros.
Rayman 2: The Great Escape
Psychonauts (not exactly for the gameplay)
Rayman Origins
Limbo

Add mighty Captain Claw! The best one imho.

This^
Great graphic and controls.
Tons of fun. :-)

Well now THERE's a question the short answer is
Prince of Persia 2: The Shadow & The Flame
http://www.mobygames.com/game/prince-of-persia-2-the-shadow-the-flame

But some people might discount the original 3 and count Prince of Persia: Warrior Within
http://www.mobygames.com/game/prince-of-persia-warrior-within
as the '2nd one' as it comes after Sands of Time which was the first PoP for a couple of years when it came out

Hells some might even call the latest one -
Prince of Persia - Forgotten Sands
http://www.mobygames.com/game/prince-of-persia-the-forgotten-sands
the 2nd one as it comes right after the 2nd reboot of the series which does that annoying modern thing of just calling itself 'Prince of Persia' like the others don't exist or something

Basically there's 8 games (so far) more-or-less arranged into 3 series
http://www.mobygames.com/game-group/prince-of-persia-series

I've only played Soul Reaver but yes that was GREAT, it has fighting parts, platform parts and puzzley parts so its probably most like.. the second Prince of Persia series (the one starting with Sands of Time)
But with less fancy 'parkour' moves and more puzzles, especially block moving puzzles

But there's mechanics in there that remind me of Zelda, Mega Man (gaining defeated bosses powers) and 'Metrovania' (using the powers to access previously inaccessible parts of the map)
So all the greats!

Have a look at Rogue Legacy. There's not much to explore -- maps are randomly generated from a rather extensive selection of fixed layouts, more difficult rooms are added to the pool as the game goes on -- but it's incredibly addictive.

Holy crap - Reading about Forgotten Sand properly
http://www.mobygames.com/game/prince-of-persia-the-forgotten-sands

Its actually an abandonment of the Cell-Shaded reboot and fits into the Sand of Time chronology between Sands of Time and Warrior Within so you COULD count it as the second game in the SECOND series, chronologically to the Prince's life story!

Lots of my favourites already mentioned, in particular Castlevania: SotN.

My favourite of all time is Wonderboy III: The Dragon's Trap on Sega Master System (was ported to PC Engine and others I'm told.) Early example of a metroidvania light, and a bit different to the other wonderboy games. If you haven't played it you go through the game defeating aspects of animal dragons, and acquiring their curses in order to be able to shape-shift into said animals.

These new animal forms grant abilities such as being able to swing beneath you to destroy blocks, swimming, flying, etc. Giving access to new areas. There are collectible spells/items, armour sets with set bonuses and weapons, plenty of secrets.

The game was way ahead of it's time in my opinion and while I know a lot of it is probably diluted by nostalgia, I'd recommend the game to anyone capable of getting their hands on it. It's a travesty that it hasn't been included with the popular SMS/Genesis emulation packs.

I'll add a list of some more when I can think of them. :D

I think I actually completed the original Wonderboy on C64 when I was a kid - ah happy memories of desperately NOT getting the skateboard on each world's stage 2 - the island hopping cloud platform one!

I also completed Impossible Mission on C64 - what a great game with amazing main sprite animation and voice synthesis (for the time and platform) THAT was!
ooh Pitfall 2 on Atari 2600!

Ahh I remember that part. I think it was either that segment and what I want to say were floating rocks? or The Last Ninja in general which inspired my first gaming related rage.

Wonderboy was the Mario of my early childhood.

Crash Bandicoot for pc?? When?? Where?? When??

I remember seeing this one! +1

Platformers (and or Platform Adventurers):

-Super Meat Boy
-Super Mario World
-Super Mario World 2: Yoshi's Island
-Super Mario 64
-Limbo
-Braid
-Sonic (1-3)
-Dynamite Headdy

Platform Metroidvanias:

-Outland
-La-Mulana
-Cave Story
-Antichamber
-Guacamelee!
-The Swapper (in a sense)
-The Metroid Titles (Fusion, Zero Mission, and Super Metroid)
-Castlevania series (Symphony of the Night, GBA titles)
-Dust: An Elysian Tail
-Zelda II: The Adventure of Link

There's a bunch of others I haven't gotten around to yet, either because I own them and haven't played that much or because I don't own them (like Trine 1 and 2, Giana Sisters: Twisted Dreams, Rayman Origins and Legends, Contrast, Valdis Story: Abyssal City, Rouge Legacy, Spelunky, etc.). This game is more like a cinematic adventure more than a platformer. A lot of the platforming that's in this game (from what I remember) is automatic. The only thing that really bothered me with this game were the controllers, other than that I thought it was good (at least for what it was trying to accomplish).

'Vessel' is a very good puzzle-platformer
Might be too 'more puzzle than platform' for some though...

'Fez' Is maybe a better mix of the 2