I spent hours playing N v1.4 in grade school, and the update, v2.0 is free online [0]. There is also a more reworked version, N++, on Steam that I can't vouch for but is probably good. There is also Dustforce [1], which has some very unique mechanics and is on Steam. Super Meat Boy [2] was inspired in part by N and got a lot of press. It has the same fundamental gameplay that N does (everything kills you, run and wall jump with physics) but not written with Flash and with some bells and whistles (I still like N and its physics better).
Also in the bucket of skill-based, storyless games is Devil Daggers [3], though it is first person, not a platformer. Some people love it, some hate it. I found it very compelling.
[0] http://www.thewayoftheninja.org/