With only my 6-year-old laptop and my brand-new iPhone, my gaming options while home for the holiday were fairly limited to the mobile platform. I found myself playing a lot of Hearthstone (and Fallout Shelter, which is fun, but in a kind of skinner-box way that is more about being OCD than really strategizing.)
I grew up playing Magic the Gathering, and while I always played more out of a sense of self-expression than real competitive edge (I created a Vampire deck back when there was only one or two vampire cards that came out every two or three blocks - before they became the default non-Zombie humanoid black creature type.)
But Magic was always a TCG - trading card game. When I first started playing, I made some really bad trades because hey, I was a kid and thought that a big 6/6 creature had to be more valuable than something silly like a Sol Ring (which is one of those cards they don't reprint because it's super-powerful, despite being kind of prosaic.)
Hearthstone owes a ton to Magic in its design. It was relatively easy for me to pick up because, for the most part, Hearthstone is "Magic, but simpler (usually.)"
But I think the really big difference is the way you put together your collection.
I'm usually pretty opposed to Free-to-Play models, because generally they're pay-to-win. Hearthstone skates pretty close to that, to be honest, but there are a few ways that it manages not to quite go over the edge.
The first way is that it's pretty easy to earn enough gold to buy packs. Daily quests will award 30-60 gold, and every three wins will get you an extra 10, which you'll get while working on said quests. So if you play regularly, you can earn a new pack every two days, or sometimes even more frequently.
That's on top of the Tavern Brawls, which often come with pre-made decks, meaning that if you play well (and are lucky) you'll have just as good a chance as your opponent, even if they've got an enormous collection.
The game was designed from the ground up to make sure that other players couldn't screw you. Individual cards aren't for sale (unless you count the rewards for Adventures, which comes with fun unique challenges that admittedly don't have a huge amount of replay value.) But because you can't trade cards, you do find yourself at the mercy of RNG with card packs. If you want to use the crafting system to make Legendary cards, you're either going to need to burn through a lot of cards or... well, hope that you get lucky with your next pack.
This does mean that "net-decking" is much more difficult. If you insist on getting all the specific cards to put such a deck together, you might need to drop big bucks to get the dust.
But I also think that fewer decks are unbeatable. A large part of that is because of the way that minions work. In Magic, as long as your opponent doesn't have spells that can kill specific creatures or wipe the board clean, you can summon your weak little 1/1 creature that has a powerful effect and simply leave them on the board, untouchable. However, in Hearthstone, if you summon someone like Baron Rivendare to make insane use of Deathrattle cards, I can always smack that guy with my minions, wearing him down over time.
Basically, those big strategy-making cards are far more vulnerable. Contrast that with Magic, where not only can creatures abstain from combat, but you can also have artifacts, enchantments, or even lands that really need to be dealt with using specific strategies or spells.
Hearthstone is unstable by design, forcing you to build your deck around themes rather than individual cards. And as a result, I believe it's easier for a casual player with somewhat less awesome cards to be able to give a good fight and sometimes win against some tournament-level stuff.
Of course, it might also be because the game is relatively new. Over time, Magic adopted special formats to ensure that players started on a relatively even level - having formats where only cards from recent blocks could be played. People haven't had the time to amass enormous collections from which they can pick only the most overpowered cards. So it's possible that the somewhat egalitarian environment of the game might only be temporary.
It'll be interesting to see.