The important thing about AI is that it has to be fun to play against. The hard part is you need AI that is fun for a wide variety of players.
some people like nasty AI, some people like easy AI, and some like RP-ing AI.
My big thing is I want an honest, good AI, that will RP some at lower levels, but be ruthless at higher levels. GCII did a good job of this.
You need to have room for all three, and this may be the single most important thing to a single-player game.
That said: question of my own, how much processing does the AI take in comparison to other stuff?