GalCiv2, with the expansions, has a very good AI and one which isn't entirely focused on total war. There are options to dedicate more CPU time to the AI to increase the difficulty. It's possibly the best AI I've seen for 4x games.
Was about to mention GalCiv2 as well. Stellar AI. I once read a blog post by Brad Wardell (of Stardock) where he mentioned he only added gameplay features once he thought through how the AI can use them properly.
Also, if you're tired of the more mainstream turn based strategy games, I'd recommend something like Hearts of Iron 3 or Europa Universalis 3.
