So what I'm hearing is Hearthstone is set around the late-BC era of WoW PvP, when priests were essentially immortal and made arena play a test of which team's priest is better?
I wouldn't really compare it with WoW. It's not WoW, it's not WoW pvp.
It is frustrating, though. The deck I play is all about battlefield control (lots of taunt minions, lots of cards that put multiple minions on the board at once, etc) and the only class I have significant difficulty with is priests. I'm probably like 2/10 against priests, breaking even or ahead against every other class. Warlocks cause me trouble too, but not enough trouble that I give up as soon as I see the Gul'dan avatar the way I quit when I see Anduin.
I play mage in constructed mode, level 15.
Deck I faced had the 2/7 troll that gains 3 attack every time it is damaged just healed and reaped in the attack damage and face raped my minions.
Don't hurt the gurubashi berserker until you can kill it. Be aware of the damage that you have on the field, and the damage that your enemy has to deal with before they can hurt you (it's worth it to hurt the gurubashi berserker right now if it means they have to kill themselves against a tank before they can hit you; it's not worth it to take 5 damage next turn if you can't kill it swiftly this turn.) It's not the end of the world to lose everything you have on the field as long as you can repopulate. In most of my games it's pretty normal for who has control of the field to change pretty quickly (as a mage, flamestrike can quickly turn complete enemy control of the battlefield around, for example.) Ideally, you should have some
method in your deck to take out a heavy hitter pretty quickly, whether that's a class spell or something like the dwarf hunter who kills high-attack enemies when it comes out on the field, etc.
Priests are fucking ridiculous because there are so many minions whose utility is based on their health bar (imp-summoner, that minion that makes new cards whenever it takes damage, gurubashi berskerker, etc); the ability to very affordably cast heals every turn makes those cards incredibly powerful, and if the enemy can't get enough damage out to kill them outright (which can be difficulty against 7 health minions like the berserker or 5 health minions like the imp summoner because they can be pulled up relatively early and buffed like crazy by priest spells) are basically super-powered in Anduin decks.
That they can summon, like, a mogu 2/7 on turn 3 and turn it into an 18/18 by turn 4 or 5 makes a lucky draw Anduin basically unstoppable by most classes ... except other priests, who can spend 3 mana to kill an 18/18. Rogues can, too, but rogues don't have the same incredibly utility in every other situation that priests do.
One of the important things I picked up on early on is, don't waste useful, cheap spells early. Save them until you need them. You can afford to take a few damage early on if it means saving your cheap game-changer spells until they're really going to change the game, etc.