These all apply to the arena. For pvp, I don't have a 'most hated deck', although since I like control decks, I sometimes get annoyed when I see nothing but rushes. (which is usually the case :p) Most rushes take little to no skill to play, and I prefer the more cerebral game of two control decks facing each other off.
1) Cremation rush deck. With double draw, the primary weakness of this deck, the card disadvantage to play quick creatures, is negated. I'm just as guilty as anyone else for posting a couple of these in the arena; I had one cremation destroyer rush that was 60-0 before finally losing a game.
2) Supernova decks. I don't know what it is, but the AI always seems to get 2-3 supernovas in its opening hand and play everything, and when I make these decks, I'll get 0/30 and just sit there discarding
Thus, I hate them on both sides of the table :p Hate seeing it in arena, and never play it myself due to the dependence on supernova.
3) Anything with Black Hole, especially #2 above. Black Hole in the early game pretty much reads 'opponent loses their next turn except for attacking', and when your opponent plays one during each of the first six or seven turns of the game... well, even a monodeck has trouble playing anything. The worst is when you have sanctuary in hand, but get locked out... :p
4) Water/death poison. My favourite rainbow deck has an innate weakness for this style. Physalia poison is only an average deck, but it really does a number on my rainbow. Most of my other arena decks have no trouble with this deck, but they aren't as fun to play.
I've never had issue with firestalls in the arena; I fairly regularly beat those. It's a good deck, but compared to the above three, it's not that great.