Guardian Legend for the NES is pretty tough just because all the clue for how to advance are so cryptic. The game plays like a shoot 'em up, mixed with over world exploration like the original Zelda game.
Also, if you want a long term, and I mean HUGE long term commitment to rising difficulty, you can try Valkyrie Profile 2: Silmeria, on PS2. It's an RPG that has a feature where each time you beat the game, you can start over at twice the difficulty as the last run, up to 50 restarts. As far as I know, no one has ever done all 50 extra levels of difficulty. That's mainly due to lose of interest whenever someone gets to about 39 or so (from what I've read on forums at least). The problem with that game, is that you won't get some of the story if you haven't played the original.
Honestly, you might get tired of the second game before it gets to some of the extremes of it's difficulty. And the first time you raise it, it only makes the leaders of enemy parties have twice the HP. But every time after, it changes more at once, other than Leader HP.
I know those aren't the toughest things in the world, but I'll try to think of something else and come back to this.