Well, there wasn't any fantastical stuff on Rome or Deadwood either, and those two series were apparently ungodly expensive. Carnivale was technically fantasy, but of the subtle variety, and again, huge price tag.
I like to think they could indeed pull off the first season on a reasonable budget, but if simply stocking a recreation of an old west town--Deadwood's only actual setting--cost as much as it apparently did, I shudder to think what the sets and costumes for this could cost. Not to mention the cast (apparently paying the sprawling cast was a factor in the above shows' budgets, too). And that's not factoring in the CGI stuff. And there are some huge crowd scenes, plus the big battle in book 2 (though that takes place in a chaotic, smoky environment, partly on water, and if I recall correctly at night, so they can probably cheat on that one instead of using LOTR-style vast armies.)
Personally, I'd be totally cool with animatronic or stop motion dragons and a matte painting for the Wall, but that doesn't seem to be how HBO rolls. The prestige generated by these series seems to demand hefty budgets and very high production values.