Holy shit, Battletoads co-op. My cousin and I would spend summer after summer trying to beat that fucking hoverbike level in Battletoads & Double Dragon.
The hardest game I've ever played and enjoyed was Ninja Gaiden for XBox. The game really forced you to get better as the game progressed; you had to learn how to use combos, magic, and all of the different weapons just to stay alive. I think Ninja Gaiden is one of the few recent games I've played where the lowest enemy can still easily kill you.
And of course every Contra game.