So excluding games that are unfairly difficult and in no particular order except when I thought of them...
Zelda 2: The Adventure of Link
Fair enough for its time. Nintendo had not made a side scrolling action game where you could swing a sword before, and it kind of shows. The penalty for failure is very high (start back at Hyrule Castle), and death is quite easy to come by. Enemies that you just encounter randomly can be mini bosses in themselves if you are sloppy with the controls, and learning how and when to use magic is quite a brain teaser.
The later games toned down the difficulty somewhat, but the first game in the series kind of has it in for you. Still, with some practice and quick reflexes, you can beat this game... it's just gonna be... well, let's say stressful.
Teenage Mutant Ninja Turtles
Ok, so it is quite unfair to simply lose a Turtle when they run out of life, and enemies have really funky collision detection rules and take about twice as much damage to eliminate as they should. But once you practice it enough, this is a game that can at least be called sort of fair, and it isn't too long either. By the end they basically are just trying to intimidate you into quitting, but the journey there is a nail biter for sure. You really need to know how the subweapons work and pay attention to how you stock up on them, while keeping all 4 Turtles healthy more or less. Still, beatable.
I can hear it now... "Spoony, you're a goony, Maniac Mansion is just a point click adventure. How is that hard?"
You could say this is simply a matter of memorizing procedure, and you would be correct...that's the whole game. But to be honest, there is a lot of crap to remember in this game, and a lot of clunky control issues that make things a little ...well, precise. You forget one little detail of what you're supposed to do, and basically the game becomes an exercise in frustration. Plus, if you've never played it before, there are a lot of things that you can do that will basically either kill the character you're playing as, and/or end the game prematurely, which you wouldn't necessarily see coming. Giving your own recording contract to the Green Tentacle is a really big mistake, for instance.
Final Fantasy III
Similar to the above entry, you can say that preparation basically solves the problems that occur in this game's 'challenge.' But having the patience and mental focus to do that preparation properly and then execute it is the challenge...not keeping your HP away from 0. FFIII was where the series took on the complexities that its battle system would become known for, as opposed to the first two games basically being experiments that played with what Dragon Quest was doing. FF2 is unfair; FF3, while pretty frustrating at the end of things, can't really be called quite so unfair as that.
Mighty Final Fight
Coming late in the NES's lifespan was a good thing for this game. RPG elements were beginning to crop up in action games, and an RPG-style beat em up was bound to happen (River City Ransom deserves its own thread, tbh). However, limits on the number of possible continues keep things fresh here, a method often used by arcade beat-em-up games that get home conversions. It will be some time before you become fast and judicious enough to defeat this game without losing all your continues.
In closing, don't forget that challenge of a game is relative. How good is the player, is a question? Some people have beaten Batman 1,000,000 times...I can't pass Stage 3 on a good day.