1. Format variants
Magic has many fun variants, most of them multiplayer: free-for-all, Commander, Two-Headed Giant, Star (or Color Wheel), Planechase, etc. Some of these were invented by players and later adopted and supported by Wizards of the Coast. One of the joys of Magic is how flexible its formats can be.
Compared to that, the single format of one-on-one battles in Hearthstone is less exciting. (Of course, Hearthstone is limited by its technology in a way that real cards aren't.) Sure, we're getting a raid in Curse of Naxxramas, which could shape up to be a fantastic single-player variant. But an online game like Hearthstone, with millions of available players, begs for multiplayer formats. They could be competitive or cooperative, playing against other teams or "bosses."
A Planechase variant could be adapted quite easily by using the different game boards, once Blizzard adds a few more. Multiplayer variants will be more tricky due to the game's current layout, but I have faith that the developers can make it work.
2. Activated minion abilities
One disappointing limitation of Hearthstone is that, once your minions are on the board, the only thing you can do with them is attack. Sure, they have plenty of triggers: battlecry, deathrattle, and unique triggers like those on Knife Juggler or Lorewalker Cho. But in terms of actively using your minions, all you can do with them is deal damage.
Why did Blizzard omit these abilities? Maybe they aren't iPad friendly enough, or maybe they complicate the game too much. Regardless of the reason, I hope Blizzard finds a way to let minions do more for you in the future. Imagine a minion that lets you pay mana to remove taunt from a minion once per turn, or a minion that can sacrifice itself to peek at an opponent's secrets.
Blizzard needs to come up with many, many new cards for the long-term health of the game. Adding activated creature abilities opens up a vast number of potential card designs and many more strategies. Even if they have to remove the attack ability from a minion to make its activated ability work, it's worth the tradeoff in terms of design space alone.
3. Diverse card types
Magic has several different card types besides creatures and spells. Artifacts are ancient items of power or new constructs created by inventors. Enchantments are magical spells that linger to have a persistent effect. Lands aren't just a source of mana in Magic but often have utility beyond their basic purpose. Planeswalkers are allies that you can summon to cast spells for you. The diversity of card types lets the designers give a card a specific flavor, with a premise that makes sense according to the rules of its universe.
Because Hearthstone only has minions, spells, and weapons, everything that sits on the board becomes a minion. That leads to awkward situations where inanimate objects like Mana Tide Totem or Summoning Portal can gain power and attack. Such cards should be classified as a different type so that they can't attack. Then Blizzard could design further cards that interact with cards of that type.
Hearthstone doesn't need to copy the types from Magic. The Warcraft universe has many concepts of its own that would make for excellent card types. Instead of land, you could summon a garrison building that gives you a certain bonus or protects your minions. A trinket card type could be activated once per turn like a weapon or hero power. Mount cards could give a minion charge and other enhancements.
4. Giving cards to new players
I like that Hearthstone is an economy of one. The cards only have value to you. You can't scam or be scammed, because trading and selling are impossible.
That said, one of the major problems of the game right now is that you start your collection with so few cards. Real, creative deckbuilding is impossible for a long time unless you spend a huge amount of cash up front. Otherwise, you must have the patience to spend weeks completing daily quests with a pool of cards that grows at a glacial pace. It's one of the main reasons I didn't enjoy the game at first.
One of the ways that I get friends into Magic is by giving them a bunch of cards to build decks around. If Blizzard wants as many players as possible, letting us give our friends some cards is a great way to keep them playing once they start. Sure, you can buy them one of the fancy new Battle.net gift cards, but those require real world money.
What's to stop this from becoming a trading service? Blizzard would have to put restrictions on when and to whom you can give cards. For example, you could only give cards to a Real ID friend and only during the two weeks after they first log in.
There's still the matter of dust, but getting more friends to play is more rewarding than crafting a few extra cards, at least in my book. And I think it would be better for Blizzard's bottom line in the long run, too.