A friend and I used to keep in touch by playing RTS Vs the AI while chatting over the mike.
The AI in most games is utterly banal and predictible, and as soon as you go past the easy or medium settings it cheats ruthlessly. Of the big recent ones (StarCraft 2, Company of Heroes 2), it's been a very disappointing experience.
For SC2, it just keeps rushing you, so you end up turtling until the AI runs out of resources.
For CoH2, again it just constantly rushes you with much better stuff that you can afford. CoH2 is actually really annoying as you can never afford anything, and so don't get to play with different units, you're always seem to end up playing the same composition.
What this means is that every game is virtually the same, you're just trying to establish a line, wait until the computer runs out of something (or uses the artifical unit cap for stupid things, effectively running out of an army), and then you roll them.
The only game I remember with a little variance was Dawn of War 2.
Maybe co-op Vs AI is something they just don't care about, but it feels as if it's got worse over time, becoming extremely predictable.