Leave it to Gamasutra to come up with a fantastic list of twenty of the most challenging video games of all time. The games on the list are fair challenges, too, and include titles such as Blast Corps, Mischief Makers, The Legend of Zelda, and a bunch of other such games both retro and contemporary.
It is forgotten sometimes that Treasure makes games other than shooters. Mischief Makers got a bum rap upon its release, but the moaners missed out on a surprisingly clever 2D platformer. And while most people can make it through the main game, the amount of the ending the player got to see depended on how many Gold Gems the player had found. Every level had such a Gem. In most levels they weren't too hard to find, but boss levels had them too, and to earn it the player had to win without getting hit. And the last one could only be earned by getting an 'A' time on every level of the game. That is not an easy task; take my word for it.
There are a few games missing from the list, of course. The older Castlevania titles are absent, as are Kid Icarus and Battletoads. F-Zero GX is nowhere to be found either. Note that the list seems to exclude titles that are difficult due to poor design. I think we can all agree that a game such as, say, Ghostbusters 2 for the Nintendo Entertainment System is difficult because the controls are a mess and the level designs are tedious. That's the unfair challenge of frustration. True and fair challenge results from solvable puzzles, solid level design, and the occasional amazing acrobatic controller feat.