I've beaten all of these on both modes, and I'll pretty confidently say that you can down the normal modes with any deck that even half-works as long as you make some personal adjustments for the bosses, although there's obviously ideals.
The heroics are pretty fun puzzles though. The second and third specifically demand you to play along the rules of the game , the third especially-so as it favors battlecry cards -a lot-. The thing is, if you just stack battlecries and cheap minions, you can actually outswarm the boss herself and just retain total board dominance. The second is easily beaten by zoo decks or quality/efficiency decks like priest with cards that involve a lot of buffing or removal while being functional on a low-card hand to avoid that ability; mind, her hero ability isn't what's scary in heroic, it's the 2/4 acolyte which gives her 3 damage a turn. You can probably run warrior just as well since she favors rampage/inner rage combo so much and just execute, but I haven't tested it myself.
Anub'Rekhan heroic is simple and you can use a variety of strategies to take him down, it's all about getting so far ahead of his hero ability that it becomes irrelevant.
The best part about these bosses to me is that they have cards that are completely unfair, which definitely makes them feel like bosses. They surpass the player with a lot of brute force and sheer size and it takes at least some thought to break through. I was really afraid the AI was going to be too stupid to make this fun, but I'm glad that I'm wrong. It's a very fun way to earn these cards (and the eventual card back, once all the heroics come out. I dread Heroic Kel'Thuzad. I dread it.)
Love this expansion though. What a fun mode, and the addition of new cards to shake up the game is long overdue. I await the next four quarters very much.
GKs value mage deck (all basic cards google it) beat the first and third bosses. Basic warlock deck beat second boss after losing once. I also failed once on the third boss. All in all it wasn't that hard. And I'm not some good player. I don't even play ranked.
I beat all 3 and heroic anub with my controll shaman. Any deck that you have been properly developing for a while should be able to take them down if you play for value. All I really crafted for that is 2 azure drakes 1 lightning storm and one wolves. The rest tends to trickle in. Anyway the first normal ones tend to make silly mistakes that cost them the game.
I was a bit lucky against anub heroic that his 2/8 taunt pulled in a fire ele in like turn 3 or 4 gave me great tempo.
boss 2 I'll maby try zoo. But all I've been hearing about the last one is aggro hunter. The AI doesn't know how to deal with traps (or doomsayers for that matter) and with all the spiders explosive trap into UTH is fantastic. After which you zerg her down with hero ability and chargers.
I feel dirty playing hunter though so I might see if I can get something together that can survive till you can cast alexstraza. maby heavy heal paladin with the consecrate pyro/equality combo. maby a priest with bouncing heal battlecries to keep you alive.
I beat them all on both difficulties with my tempo rogue deck. It wasn't even challenging, just a consistent rofl stomp. The only one who made me sweat briefly was The Grand Widow because I only drew minions with one health early on which her hero power absolutely shits on.
The two class challenges also felt quite easy. Maybe I just got good draws but it seemed like the custom decks were almost designed to counter their opponents. For example, the rogue deck is based heavily around bouncing your creatures for extra value. The opposing hero's power bounces your card for you!
Overall, while they were fun and the new cards are pretty cool, I hope the next bosses are a bit tougher. Also, before everyone goes saying that I'm probably just using a deck that's filled with epics and legendaries, no. It's mostly utilizing rogue's best commons (Backstab, Eviscerate, Deadly Poison) while having a few high quality rares (Azure Drake, SI7, Argent Commander). It's basically meant to make beneficial trades so that you always have multiple options and always stay ahead in board presence. It seems like these boss decks have a tough time regaining board control.
I found the standard bosses pretty easy - I made an NA account the day before, and managed to beat all 3 with a really cheap Paladin deck made only of cards I found in the free packs it gives you. As for Heroic, Anub'Rekhan was a challenge, but I beat him first try with my dumb legendary-filled ramp druid, and Faerlina was trivial once I decided to switch decks to Zoolock. Maexxna, on the other hand, was a huge challenge, and I found it really fun to try and engineer a deck that could beat her. There seem to be a lot of variations on the strategies you can use, but all of them have a recurring theme of cheap, solid battlecry minions - especially Voodoo Doctor, Earthen Ring Farseer, Mind Control Tech and Elven Archer. My deck also had some board clear in the form of Auchenai/Circle and Holy Nova (I was running priest), as well as two Knife Jugglers that worked really, really well as a finisher once I'd reduced her to topdecking. I'm definitely excited for what the next few weeks will bring in terms of these challenges, as these were a lot of fun :)
A nice cheap way to beat Maexxna is to use a Paladin with 2x humility, 2x peacekeeper, 2x earthen ring, 2x guardian of kings, 2x elven archer, and 2x voodoo doctor. Use your healing battlecries to keep your health up, and keep her board filled with 1 damage minions. 7 damage a turn is out-healed by turn 8 with Guardian + Voodoo Doctor, then Guardian + Farseer by turn 10. Then just fatigue her out ;). Keep draw cards out of your deck or you'll risk killing yourself with fatigue. Fill it out with Holy Light, Truesilver, and low cost spells like Hand of Protection and Blessing of Might to keep your hand size low so you can draw into your heals.
Just the fact you can try over and over until you get the perfect draws makes almost any decent deck a possible winner. I beat all three heroic with my only legendary being Leeroy Jenkins, though any decent charge card would have been as useful.
Used a Hunter deck using the old call of hounds strategy despite the cost increase, beat all three bosses on first try, the heroics are handing me my ass though. Definitely a challenge but at the same time I can see myself being able to beat them, brilliant balance.
Beat all with just Maexxna Heroic left, that 0 Cost Ability, really forces you to adapt to counter.
yeah, need to make a deck filled with damage battlecry minion.