There's a
list of the "30 hardest NES games ever" from 2011, but it could use an update. Overlord is quite easy to beat, for example, and Star Voyager isn't especially hard at all. Dragon's Lair has an incredibly nasty final boss but otherwise isn't too difficult once you learn the game. Even so, beating most games on the list -- really, anything except Overlord -- would still be a bragworthy achievement.
Besides Ikari Warriors, I'd say that Mutant Virus, Q*bert, Arkanoid, To the Earth, and High Speed are a few of the games that have emerged as strong candidates for the hardest NES game. I'd throw in The Last Starfighter too -- I found it almost unplayable, and that's coming from someone who's beaten a Uridium clone on the CD-i (Steel Machine), though that game at least lets you save after each level. No doubt someone else has figured out TLS better than I have.
Of course if we're talking about "rite of passage" games, then beating Blaster Master is maybe the biggest one I haven't done yet. And yeah, I too have a hard time telling whether games like Contra, TMNT, and Mega Man are really hard since I've played them so much.