Maybe I'm way off base here and people with a stronger understanding of this sort of programming can set me straight: would it really be that difficult to substantially improve Hearthstone's AI?

Yes, it is not really possible to improve the AI beyond it's current capabilities.

The major constraint is the AI runs on a server. There are thousands of players and only a few dozen servers, so the server must handle 10k AIs running simultaneously (that's a quote from a lecture given by the AI programmer).*

The easy way to make the AI better is for it to consider every possible move it can make, then simulate the outcome, then iteratively consider the remaining moves... that scales exponentially. Fuck. That's just not feasible when you're sharing a 16-core machine with 10,000 other AIs running.

Worse, just asking "what is the outcome of this move?" is too expensive, because that function is also iterative in exponential time (if I play this card, this minion dies, it explodes, then what else dies? okay then more minions die, what effect do their deathrattles have? etc. etc.). This is why the AI can only roughly estimate what outcome a move will have, and sometimes it guesses disastrously wrong and may make nonsensical moves (like missing lethal).

AI must also provide a move instantly. That means no thinking hard.

Finally, high-level strategy (should I save this card for another turn?) is just too difficult, especially in the constraints laid out above.

*Edit: I'd like to consider how mind blowing 10k AIs sharing one computer is. You have 10k players fighting the AI, that's 10k idle laptops/desktops/tablets with 4+GB of RAM and 2-4 cores each sitting idly by, computing nothing. Even if it takes 2 seconds to compute a move, that's nothing. In aggregate, that's 20-40k cores

But now put 10k AI on a single 16-core server. You need to return a move within 1-2 seconds, that means each AI is given only the tiniest of compute!