I'm very for the golden middle. I don't mind a challenge, but if a game feels impossible right off the bat (like AoL did), it puts me off wanting to even make a proper effort. Like Iridescence said, it's not fun having to replay something over and over again because you keep dying and have to start again from the beginning. In general, punishing difficulty is never fun for me, it lies in the word "punishing" - I like being challenged (it feels rewarding when you finally figure out that one thing you need in order to progress), but I don't like being punished.
But the complete opposite is also not fun. If it's insultingly easy, like you keep getting the solution handed to you regardless whether you asked or not, or you just don't have the option to fail (I have played games where you don't even die, you just faint and get back up again mid-fight and continue).
But for me, the thing that makes me hate overly difficult games more than overly easy games is that, when it comes right down to it, at least with the easy games, you can still play them, can still experience them. Difficult games that doesn't allow you to experience anything before you're killed, you just don't get to know what they have to offer before you feel like chucking the controller away.