Meh, I don't agree on so many points.
I don't see how it is "very, very similar" to Magic. I'm talking paper/MTGO Magic here, gameplay and metagame is so, so much more complex that I don't really see the compassion. I didn't really play DotP, only watched some of it on youtube, and while it is basically "a tool to learn the rules of magic" its still more complex than HS.
HS is very simple, and it turns out that that isn't such a bad thing after all.
It being more streamlined, I agree there.
I also agree that it has quite more "random" spells than usual. Thing is you play around it to maximize that "random" will actually be in your benefit. For example, the minion that you mentioned, you try not to play it when it can either "win or die" but when he has 4 equally strong minions. Yes, sometimes you win or lose on the "fluke luck", and that can be not-fun sometimes. Your luck averages out in the end and it's how well you played around your luck that gives you most wins.
As for drawing your only out (Fireball), well, that's the nature of TCGs/CCGs. Again, you play around it. You know what your chances of drawing a fireball are. So does your opponent. You always play it so that you have as many outs as possible that you can draw. You always play so that you give your opponent as few outs as possible. Sometimes, your only out is a Fireball. Yes, sometimes you topdeck it, but most of the times you don't. Yes, it sucks for your opponent who probably played good and left you with only one out to lose, but well, that's what you get when you sign up for a card game. The former argument of "it averages out" still stands.
Other thing is that topdecking an only out is so fun. I mean, some of the most iconic moments of Pro Magic are exactly those - winning against all odds.
As for deckbuilding - I think you are way overestimation Dominon's influence on CCG world (which is non-existent). And honestly, you cannot compare dominion's "up to 10 of any card" with CCGs. In Dom, you actually need to work hard to both acquire the cards and make the deck consistently draw it. Acquiring cards is 0 work in CCGs (gamewise) and if you can put as many in as you want, drawing them consistently is a breeze. It would be like you had a premade deck in Dom (which would suck). Moreover, limits are need to actually some archetypes/decks (combo for example) viable but not overpowering.
Also, limiting cards to classes actually makes for more creativity, imo. Firstly, they need classes to catch that WC feel. And the only way to differentiate between them is to make some cards available only to certain classes. It's "creativity under restrictions", and it's been in CCGs from the very start. Hell, that's what dominion is all about! Isn't dominion more fun exactly because you don't have everything available in every game? That's the feel that they want to get too.