Some of my favorite platformers:

Another World

http://www.youtube.com/watch?v=ba8-SlkUIwc

Bionic Commando

http://www.youtube.com/watch?v=KDA4giB7Klk

Blaster Master

http://www.youtube.com/watch?v=_HTfQRshDTU

Braid

http://www.youtube.com/watch?v=NdUyHi1i2h0

Castlevania: Aria Of Sorrow

http://www.youtube.com/watch?v=HjTlzSDUshc

Castlevania: Circle Of The Moon

http://www.youtube.com/watch?v=lfopPvUP_FI

Castlevania: Harmony Of Dissonance

http://www.youtube.com/watch?v=siIAivGSySs

Castlevania II: Simon's Quest

http://www.youtube.com/watch?v=g7AjPRCVsxg

Castlevania: Symphony Of The Night

http://www.youtube.com/watch?v=d2JsYKbWubY
http://www.youtube.com/watch?v=oL3043Ms_Is

Cave Story+

http://www.youtube.com/watch?v=vlLiE9iubOk

Contra

http://www.youtube.com/watch?v=AcAqo_fC89I

Contra: Hard Corps

http://www.youtube.com/watch?v=-9YFtbCb3y0

Contra III: The Alien Wars

http://www.youtube.com/watch?v=JDW2IMnVDvA

Contra 4

http://www.youtube.com/watch?v=7GSRFZPO3ZI

Demon's Crest

http://www.youtube.com/watch?v=qhTnJef0pt0

Donkey Kong '94

http://www.youtube.com/watch?v=7qNvux9KT3Y

Donkey Kong Country

http://www.youtube.com/watch?v=whp2Y_MjTXs

Donkey Kong Country 2: Diddy's Kong Quest

http://www.youtube.com/watch?v=ryM1lxnSjuM

Donkey Kong Country 3: Dixie Kong's Double Trouble

http://www.youtube.com/watch?v=_q1z7HJPNmo

DuckTales

http://www.youtube.com/watch?v=ToVcSY002Gg

Dust: An Elysian Tail

http://www.youtube.com/watch?v=oQppr8bA8tI
http://www.youtube.com/watch?v=y4klwuJJZ7g

Earthworm Jim

http://www.youtube.com/watch?v=49puptyIPVI

Earthworm Jim 2

http://www.youtube.com/watch?v=b9dX_QcqSf8

Escape Goat

http://www.youtube.com/watch?v=Gh-Dzq9ztWc

Fez

http://www.youtube.com/watch?v=7MrJZ-qvfak

Flashback: The Quest For Identity

http://www.youtube.com/watch?v=phd9sDohxB4

Hard Corps: Uprising

http://www.youtube.com/watch?v=ZCGAYoaTw-0

Heart Of Darkness

http://www.youtube.com/watch?v=MNJIHNKHw_4

La-Mulana

http://www.youtube.com/watch?v=g0T1djocUk8&list=PL5BF84C13C736781F

Limbo

http://www.youtube.com/watch?v=qa1P2NuyeYI

Mark Of The Ninja

http://www.youtube.com/watch?v=EP9D1WxxWIs

Mega Man

http://www.youtube.com/watch?v=zUMs71-JkeM

Mega Man 2

http://www.youtube.com/watch?v=GZXD4v7Lqew

Mega Man 3

http://www.youtube.com/watch?v=e8GtqRlDF1k

Mega Man 4

http://www.youtube.com/watch?v=xG8V3bDSoe4

Mega Man 5

http://www.youtube.com/watch?v=HzRyVXuCmvE

Mega Man 6

http://www.youtube.com/watch?v=ZCk-u_3ME7c

Mega Man 7

http://www.youtube.com/watch?v=CHjiUOQ_4dg

Mega Man 8

http://www.youtube.com/watch?v=nWNoUlokaBY

Mega Man 9

http://www.youtube.com/watch?v=ydSl55Ee1xQ

Mega Man 10

http://www.youtube.com/watch?v=WrYwAMKCBaE

Mega Man X

http://www.youtube.com/watch?v=1GkTm3ci_TI

Mega Man X2

http://www.youtube.com/watch?v=4oHHEX-MiIs

Mega Man X3

http://www.youtube.com/watch?v=xlxTOAJ-rQs

Metroid

http://www.youtube.com/watch?v=aTHMiuubUDw

Metroid Fusion

http://www.youtube.com/watch?v=eEV5db6ICoo

Metroid II: Return Of Samus

http://www.youtube.com/watch?v=zx6wTwGMka4

Metroid: Zero Mission

http://www.youtube.com/watch?v=zo3tUABgKn0

Oddworld: Abe's Exoddus

http://www.youtube.com/watch?v=JiLbGQMEgBc
http://www.youtube.com/watch?v=GunzOExeYb0

Oddworld: Abe's Oddysee

http://www.youtube.com/watch?v=Rlo8Cotvz_E

Outland

http://www.youtube.com/watch?v=FHGxfXkoAGo&list=PLMGuirk6GNVPLrwVZJusaSOds4WeyT-ET

Prince Of Persia

http://www.youtube.com/watch?v=SrKDeNT1ofY

Prince Of Persia 2: The Shadow And The Flame

http://www.youtube.com/watch?v=mCRCmqTGhjI

Sonic The Hedgehog

http://www.youtube.com/watch?v=cEF_QUllR2k

Sonic The Hedgehog 2

http://www.youtube.com/watch?v=kM6tcf2BIOk

Sonic The Hedgehog 3

http://www.youtube.com/watch?v=KsZzxnyoNHA

Super C

http://www.youtube.com/watch?v=qYOzfuIReyo

Super Ghouls 'N' Ghosts

http://www.youtube.com/watch?v=KBRkqsX-YR8

Super Mario Bros.

http://www.youtube.com/watch?v=PNwqKW2i_RE

Super Mario Bros. The Lost Levels

http://www.youtube.com/watch?v=5apu4ML9Wto

Super Mario Bros. 2

http://www.youtube.com/watch?v=QjxtIcNIez4

Super Mario Bros. 3

http://www.youtube.com/watch?v=H1Ui3ZDX9MI

Super Mario World

http://www.youtube.com/watch?v=j8YFxB6rYIo

Super Mario World 2: Yoshi's Island

http://www.youtube.com/watch?v=8UZt8a91iho
http://www.youtube.com/watch?v=0OCOWyKAfnQ

Super Meat Boy

http://www.youtube.com/watch?v=MSJxFfHkD4Q

Super Metroid

http://www.youtube.com/watch?v=8RHV8bud6fE

The Swapper

http://www.youtube.com/watch?v=3Pbf2l6UYGk

Thomas Was Alone

http://www.youtube.com/watch?v=gRAssGQzszg

Trine

http://www.youtube.com/watch?v=TIUsSH8OCeE
http://www.youtube.com/watch?v=RUewQgZkwgA
http://www.youtube.com/watch?v=iHVAg4qydFg

Trine 2: Complete Story

http://www.youtube.com/watch?v=W2gaQ7sxda4
http://www.youtube.com/watch?v=-QFxv6oZ6vI
http://www.youtube.com/watch?v=yu4zy3FNT6M

Unepic

http://www.youtube.com/watch?v=JklTwF3ZcaU&list=PLF7F5182BC458BC4E

Valdis Story: Abyssal City

http://www.youtube.com/watch?v=4-1yMzVwHBQ&list=PLPbLKj9QfTce7gIPP350Pja17-2HOjSaz

VVVVVV

http://www.youtube.com/watch?v=KP3A_Mv17uw

Yoshi's Story

http://www.youtube.com/watch?v=-Xcx2H_5b1Q

Zelda II: The Adventure Of Link

http://www.youtube.com/watch?v=xVnYiVK-Du4

I gave you my Samus Christmas avatar didn't I?

^ this, right here!

Also Cave Story + and Soul Reaver

yes

Contrast is excellent in it's story telling, setting, visual style, audio (voice acting/music) and general uniqueness, and it does show a lot of potential. At times the game feels harder than it actually is due to finicky controls and it's sometimes overly complicated control scheme (that can't be changed), with those two things combined, certain puzzles become an absolute chore. However with all things taken into account, I have no problems recommending Contrast.

My favorites are:
Treasure Adventure Game
Flashback
Bio Menace
Realms of Chaos
Dust: An Elysian Tail
Cave Story
Super Metroid
Castlevania: Symphony of the Night
Castlevania II + III
Contra and Super C
Faxanadu
La-Mulana
Valdis Story: Abyssal City
Ainevoltas 2
Commando (by Fallen Angel Industries)

Some of my all time best platformers:

Cave Story
Rayman Origins
Oddworld: Abe's Exoddus
Out of This World or Another World
Psychonauts
Prince of Persia 1&2
Wario Land II
Donkey Kong Country 2
Sonic and Knuckles
Rocket Knight Adventures
Ducktales (wohoo!)

Favourites: Castlevania Symphony of the Night, Super Metroid, Valdis Story Abyssal City (relatively short but has replay value due to multiple characters)

I also highly recommend The Swapper. It has a thought-provoking story, atmosphere is superb and fitting and some of the puzzles are dead-easy in execution but require some strategy to complete (my favourite as I hate hard executing puzzles).

Unepic is also great but it's more of an adventure. Low brown humour in many places but the best part is the relationship between the main character and a certain fellow (play and you'll find out!).

I must be one of the few that enjoyed And Yet It Moves. I've seen many people call it pretentious (which, honestly, is a word for people that don't understand or like someone else's art or to put down hipsters) but I thought it was interesting, challenging and the art design is peculiar.

Mark of the Ninja isn't your typical platformer but it plays like one but with stealth. Awesome game especially if you like ninjas!

Thomas Was Alone is an excellent, simple but elegant strike of narrative-platformer.

Trine 1+2 Great narrative and it feels original even if it's anything but, fun adventure-platformer nonetheless.

Gateways Great puzzle-platformers but the last one is so freaking hard, I don't think I'll ever finish it.

I really love the idea of what you're saying about The Swapper. I mentioned before that I thought I had it, and HAPPY DAY, I DO! Will dl now! I'm also downloading the demo for And Yet It Moves. Added a couple more to my wishlist besides these, too :D

Based on your words about The Swapper, I really recommend Nihilumbra if you haven't tried it yet. Absolutely wonderful, atmospheric, and thought-provoking. I don't know if I'll ever finish the Void (challenge) mode, but I've done the story portion twice, and I'm ready to play it through again!

I have and I liked it especially the protagonist's struggle.

I played the demo for 30 minutes, and I like it! The problem is that it is killing my wrist and shoulder (turning the playing field) so I won't be able to continue. Thank you very much for the recommendation, though! Hopefully someone else will see this and try it based on your info :D

- Brothers: A Tale of Two Sons - can only be enjoyed with an Xbox360 controller, there are issues with other types and with mouse and keyboard controls (that's why I can't comment on it despite owning it :( )

- The Cave - is alright, but a bit simple and repetitive in the puzzles, and you run around quite a bit, to and fro, without doing or seeing anything interesting on the way (IMO the paths should have been shorter or the rooms and corridors more detailed, with more things to do or look at). The storytelling is better than the actual gameplay. You're also encouraged to play through the game several times with different characters to experience each of their stories, but since you always have to choose parties of three and the overall number of characters is not dividable by three, you'll have to repeat one or two stories if you want to see all of them.

- Dust: An Elysian Tail - I loved it. The combat is quite simple and often not that challenging, but I found it satisfying nevertheless, and what's addictive about it is the metroidvania gameplay of searching for secrets and unlocking new areas.

- Lume - is not a platfomer. It's a pure adventure or rather puzzle game (think Myst or Puzzle Agent), and it's also very short.

- Psychonauts - awesome and very original game that's great fun most of the time, with some frustrating moments in between (mostly due to controls and a checkpoint system that forces you to restart a level when you quit halfway through)

- Stick it to the Man! - quite similar to Psychonauts in style and theme, but 2D and also more of an adventure than a platformer. You jump around a bit, but the challenge (if you want to call it that, as the game is rather easy) is more in the puzzle solving. I liked it though, a little more than The Cave.

Personally I found SteamWorld Dig quite addictive. And despite their simple looks, Escape Goat, VVVVVV and, surprisingly, Rico: A Tale of Two Brothers are pretty solid and enjoyable platformers. I also like Super Panda Adventures (despite tedious boss battles, the rest of the game is very cool though) and the freeware platform shooter Iji.

That is all very helpful information, thank you very much! *goes to remove Lume from the list*

I second the mention of Limbo.
Excellent platformer, very atmospheric, but rather short.