Honestly, I feel like millhouse is potentially a lot better than people give him credit. I think most people haven't tried him out, or played him in the right context.
I ran him in a pally aggro deck right when naxx came out and won nearly every time I got him out at the earliest point he can be. At that point, the chances of your opponent actually having the spells on hand to tear you apart are unbelievably low. The chances that those spells will also have synergy with each other and NOT cause a drastic card disadvantage are also insanely low.
Spells have a variety of uses, but their primary use is removal. You play a minion that opens a potential floodgate of removal... worst case scenario your board is cleared and you lose some health. That's not game ending on turn 2 (it can be... but not always). The best case scenario is, you have a huge tempo gain on turn 2 that for an aggro deck will snowball.
If anyone in here plays oil rogue (or even played miracle rogue), consider this: what if millhouse is played on turn 2? Okay... so your backstabs didn't change if you were lucky enough to get them, you can save 1 mana to use deadly poison, which still doesn't kill millhouse, you save 2 mana if you're lucky enough to have both deadly poisons, which would be highly inefficient and rob you of deadly poison the rest of the game. Eviscerates are now free, except you only need one, using two is just silly.
Mages are a bit scarier as control mages will typically stock pile removals and secrets. Worst case scenario, mage uses fireball for free. As far as the balance between resources and tempo, playing millhouse and losing him to a fireball roughly balances. But what are the chances the control mage actually has a fireball, let alone a fireball and say, pyroblast, on turn 2?
I probably wouldn't play him against a control priest, but even control priests have limitations on turn 2.
The truth is, Millhouse is never played around, never anticipated, and has always proven to be amazing for me when used early. Sylvanas is wonderful for control, millhouse is godly for aggro.
EDIT: That being said... reading the rest of the comments, van cleef is probably better (though I don't think you need to worry much about a rogue using a super powered van cleef from millhouse in the early game). Also I'm not saying millhouse is the best epic ever in existence, as he's fairly poor when compared to other options. I'm just saying, he definitely, in my opinion, is highly under rated.
Edited by Clandestiny on 2/19/2015 8:22 PM PST