Comparing the games to chess is not entirely a good correlation.
While in a sense it's true that in a game you got more options (build 1 of 10 buildings on 1 of 10 colonize-able locations and move to 1 of 10 locations instead of which of the 8 peons to move, and 1 or 2 moves for the first turn), you can also mop them a lot better- out of the 10 buildings, only 3 actually worth building. from the 10 locations, 2 are different and better than the rest in all respects, and out of the 10 movement options you do not want to stay put, so it's actually 9 options instead of 10. The chess still has 16 options. 3*2*9=54, which is 3 times as many play options, but in order to decide which one to pick you will usually need to look at 3 turns ahead, not 10(as "the further i look the better" goes in chess).
This refinement of looking only in the near future with certain goals, and on the further future with a bit different goals means that overall many of your choices are predetermined as "best course of action", which means your option narrow down very fast.
Regarding the AI- I'd like to know how much time/developers are really put onto the issue. Brad said that the reason GalCiv has great AI (personally I didn't connect with GalCiv) is because he worked on it for years. On many of the games, you build the game, fix it up a bit and ship it. You got literally hundred of hours(if not more) built into things like the Graphic Engine for it to work, with extra time for people to use it. You got more time spent on building the game, combining it with the graphic engine etc. But considering that the game can be "played" as anything beyond meager testing only in its late stages, the AI development starts only near the end.
This also means that it doesn't get the love it deserves before shipping, and doesn't tend to be a priority.
As a "bonus feature", how much is the expected return of the AI? According to brad, investing to raise the AI from being challenging to 90% of the player-base to 95% of the player-base is not worth it.
Getting into hardware issues is not really an issue, I do believe you can free that much with good coding after seeing a video of a couple of guys talking thro a skype-like system at the 80's (which means they did on something like 56K bit connection at most), or the assembly 4K intro competitions. Both examples shows how wasteful our usage of our resources is, and that we can do better, much much better if we ever so wish. (with the obvious problem of investing time in it)