Yea micah Thats pretty standard for the genre. I don't think I've ever played an RTS or RPG where harder difficulties means smarter enemies. Harder just means enemies who get more resources and build everything ridiculously fast.

I can often level past Nightmare AIs.  The trick is to (a) aggressively hang out near where their creeps are dying, even if you're too weak to fight, ( kill them whenever possible (dead AIs don't level), and (c) last but not least, hang on to XP flags and buy the first XP upgrade ASAP; the AI still doesn't pay enough attention to these.  (the +XP favor item can also help, but I find it better to take a +damage item so that I have a better shot at killing them early on)

Killing the nightmare AI can be tough because of its HP and +HP bonuses, but you can often lure them into your towers and kill them there, esp. if you have some slow or stun effects.  It's easier with some Demigods than others, too: you need to be able to put out serious damage in a short period of time to overcome their HP regeneration (especially if they pick up some items that boost it), so the Unclean Beast or the Rook are easier to pull this off with than, say, Regulus or the Queen of Thorns.  You definitely don't want to take on more than one of them at a time until you have a significant lead in levels and gold.  And don't let them kill you if you can avoid it -- that stops you levelling and gives them gold to go make themselves even more terrifying.  That often means running away as soon as you're a little damaged, if you're fighting a Demigod with a serious damage ability (like the Torchbearer), or if a second AI shows up while you're fighting the first one.

I think adaptive might be another good word

I'm well versed in AI programming and how common it is to use cheating on the part of the AI instead of programming a better AI (more cost effective).  I was only curious if the AI in this game did that so I knew if I was doing something wrong or not.

As a student in French Literature, I'm a total n00bette in what concerns A.I. programming. My opinions, here, are consequently only worth 2 cents.

1. Micah, it appears to me, points in the right direction : COST. It's much cheaper & faster, in terms of paying person-hours of A.I. design & coding and of overall development time, to invest in cheap cheats, instead of hiring specialized A.I.-programming human geniuses who will spend a lot of 12-hour workdays designing & coding.

2. When we play against comps & bots, we're not really playing against relatively dumb machines : we're playing against human programmers.

If we beat the A.I., it's not really because we human gamers are "too smart", it's mostly because the human programmers were not given the time (paid person-hours) to refine & test more complex A.I. strategies & tactics.

We never really play against autonomous Cybernetic Intelligence. We play against human coders. 

3. There's also the limitations of the customer's computer. Even if the human developers & coders were given the time to design & program very sophisticated A.I. adversaries, it would lead to a commercial disaster :

Not only because it would have cost a lot in salaries, but also because 99.9% of the customers' computers would not be complex & fast enough (per second) to process the numerous, sophisticated instructions, which would require a lot of computations.

Games would have to be designed & optimized for full use by dual-core & quad-core machines, and even then, it would not be enough. There are no "petaflop" computers available, yet, for gamers (unless they work in some Pentagon basement).

4. Everybody who knows about the Galactic Civilization 2 series knows that it has the best non-cheating A.I. in PC games of Strategy. The series offers many levels of difficulty, and the A.I. gets bonuses only at the topmost levels. The principal A.I. designer of that series could afford to invest man-hours of his time into refining the A.I. because he owns the company (Stardock) and enjoys doing A.I. programming. Most other game developers do not have the cash and the time to do that.

Consequently, those of you humans who believe that you are "too smart" in comparison to comps & bots do not take into account the limitations of A.I.-programming investment ... and of your relatively too slow & simplistic home computers.

/my 2 ¢