I'm not sure if these games are what you're looking for, but several spring to mind Conquest of the Aegean and the games from AGEOD: Birth of America and AGEOD's American Civil War.
The games themselves are not graphic heavy, but still look good. Much attention has been paid to the AI.
Here are some links to their forums which may provide an indication of the style of each game.
http://www.ageod.com/forums/index.php
http://www.matrixgames.com/forums/tt.asp?forumid=123
These are grognard-level games and award winners at that. I play quite a bit of single player games and need some challenge. I'd put the AI from both these games at quite a high level.
If you are interested in Chess, Rybka (http://en.wikipedia.org/wiki/Rybka) seems to be the top AI at the moment for personal computing.
Bookmarks