Ninja Gaiden Black and Ninja Gaiden 2 on Master Ninja. I don't know what the hell I was thinking, but I jumped right into it without doing a normal runthrough first. I died more times than I can count now, but man was it worth it when I got to the credits in both games. Worst part is, I did it on a friend's 360 while mine was in for repairs, so no achievement for me! (This was before I knew you could download your profile to other 360s)
DMC3. I literally cried playing it on Dante Must Die mode. That game has no problem making you feel worthless, but totally worth it if you can make it through the whole thing. And I'm not talking about the Greatest Hits edition where they toned down the difficulty.
And of coarse there's the classics such as the early Megaman games, Castelvania(s), and Gunstar Heroes. I like a good challenge!