I hope the upcoming Nitrous engine (not in GC3) can do for strategy games what the Unreal engine did for FPSes.
So we got flashy strategies where everything is scripted, where missions are corridor-like and, at the end, we'll get missions with dogs? Eh... We already had Red Alert with dogs. 
Bottom line for me on AI is i desire a real challenge, the real possibility (even probability of losing) yet the possibility of winning if I am clever, sneaky, and/ore creative enough with the suite of tools I have.
Have you tried Myth series? It's more like "tactical" game, but it may provide you droids challenge you looking for.
We live in the world where it's much easier to do simplest mathematic, adding health, damage, and ability usage frequency, forcing players to calculate better damage per second per cost and looking for best counters. It also could be interesting task for that interaural ganglion, but that's more from "excel simulator", I agree.
Love it when the AI out maneuvers me, or pulls a combo I did not expect.
Good luck finding those. Guess the main source of games where we see that will be games without any building, where we could operate only with units we have at hands. Yet even there we could have those "mathematical" things.