Battletoads and Ninja Gaiden are far too easy to put on this thread, everybody knows them and how hard they are. I've got a couple myself. First and foremost I say Ikaruga since part of the challenge is trying to get something other than a freaking C for your grade at the end of each stage!
Another really hard game is Resident Evil 1 while playing as Chris. Seriously, Chris gets @#$% for ammo and inventory space, and the shotgun is tougher to get since Barry doesn't save you like he does with Jill (you were almost a Jill Sandwich!). Seriously, Rebecca is $%&*in' useless.
Also, let's not forget the game that was pulled from Japanese arcades thanks to its difficulty, Gradius III. That game is unholy in its difficulty, This could be applied to any Gradius game, but Gradius III gets special recognition.