I think mage is rather easy, since you can draft multiple viable archetypes. Elemental/Lich, Big Spell/Burn, Singleton all worked for me! Warlock is also quite easy. Just keep in mind that you should draft for the last two bosses instead of bosses 3 to 6.
The four quickest for me were rogue, shaman, warrior and hunter. You can go pretty smorc-based with all of them I find. With the captured flag +1/+1 it's easy to fill a board and overwhelm most bosses. I will admit that I pretty much took the minions don't cost more than 5 whenever I could, but it didn't always pan out as sometimes not having early plays and just big minions can lose you it outright. Mage, priest and druid took me an absurd number of plays to complete.
I got Deathrattle Hunter first try, Deathrattle Pally second try (Val'anyr OP), Jade Shaman second try, and Big Druid second try (techinically third, but I conceded after the very first game on the second run)- all the others took a bit longer. Probably my favorite run was a C'Thun Rogue deck with double Battlecries and Boots of Haste.
Today in my free brawl pack I got Barongeddon, then I had a cup of fresh green tea. As a result of that, I think Priest is OP because my keyboard is not a mechanical one. I hope Blizzard will address this issue.
I don't think that there's a definitive answer in that "this deck is better than that deck" sort of answer, so perhaps different question might be which treasures or buckets seemed apt per class.
For instance, before I got a 9 class clear I was focusing totally on the jade classes and not getting the buckets for them. Experience over time will let you know which treasures and cards work best with certain classes. Stealth for instance is great for warrior and priest but maybe not rogue.
Reading widely helped me out a lot here too. Kripp has some Dungeon run videos that'll be useful.