You need to get at least a bit lucky with your draws. There's a ridiculous amount of secrets in your deck and if you draw them all up front with no meat to back it up, it's very easy to gas out and get overrun. It took me 3 tries.
I've beaten every boss 1st try on one account, and had a few problems with the last two on another.
Main problem with Proudmoore really was Eye of the Storm. If you have a somewhat decent start, the hero power can be checked. But going against a wall of taunts two or three times, and you just run out of resources. And if you ever let a ship survive, you are pretty much dead.
The last boss is just dumb. What good is a hero power dealing 5 damage to a minion, if your opponent plays no frigging minions?!!!
It seems like they use Book of Heroes to recreate constructed experiences and give you a shitty matchup to increase difficulty. For Mage, some genius had the fantastic idea to let you play against (almost unchanged) Wild Secret Mage with a super slow crappy value deck, and in this one, you play with essentially a bad Secret Hunter against Control/Big Warrior, where most of the game is just armoring up and clearing the board...
If I want to see that, I just play Wild against BS Priest. Or not. I usually concede automatically when I see Priest. And I seriously consider quitting Wild for good, as soon as Zephrys the Clown disappears from Standard. Just one game of "hmmm... hmmm.... I wonder... I must choose quickly! ... hmmm... We're gonna be rich!" is enough, and I want to quit Hearthone and throw my laptop against the wall and see it shatter into a thousand pieces...
But in all fairness, at least the AI doesn't waste your time on top of playing nothing but clears.
Btw. what was the hardest solo content ever in Hearthstone? Heroic Naxxramas? I can't even remember them all...
"The Amazing Reno" gave me more trouble than anything in Hearthstone history. His hero power seems bugged. His 7 and 8 mana spells most certainly didn't cast a random spell; they repeated themselves every single time, and when you're talking about Greater Arcane Missiles and Power of Creation, the game ends very quickly. I had to use a cheese Knife Juggler combo, and even then it took me about 20 tries because I was constantly dying before turn 7 even with tons of healing.
I've beat Dealin at second try. In both of the games I had to empty my hand quickly, while Proudmoore had 5-7 cards in hand, and I almost lost on second try too. I also lost once against the last boss, despite I thought it will be super easy (his Hero Power was a joke compared to the one player get). At second try it was indeed easy, but at first try I had the same issue as last time: my deck lacked any card draw/generation, so I ran out of resources quickly, and he overwhelmed me with those guys summoning 2/2 which attack immediately
Definitely card draw depend. First dry - no chance Second try was easy. Killed him on turn 9.
Turn 1: nothing to do
Turn 2: Secret
Turn 3: The masked Guy that gives another secret
Turn 4: Hyena
Turn 5: Hyena
Turn 6: Bloodhoof
Turn 7: That Bow that calls 3 snakes
Turn 8: can't remember
Turn 9: Kill command
He had bad draw. PLayed only a couple of minions. he cleared the boeard on turn 8, so i had the bloodhoff (deathrattle), the bow an a kill command (5 dmg cause of the snakes called from bow) to finish him.
Hope this helps a little. I would mulligan hard for the hyenas.