Re: Grand Strategy
So this is my specialty as far as PC games. I believe the genre title you're looking for is "4x" though personally I would differentiate the 2 to some extent between war games and more empire/expansion games (the industry seems to group them).
The problem is my most preferred stuff in the genre is usually the least likely to have a multiplayer community due to excessive depth. Unfortunately I usually find AI underwhelming as most studios for these games don't have the resources to make good ones, so then I find myself going more mainstream to get decent opponents for these types of games on multiplayer.
We actually have a hamachi network in our area that we run 4x on pretty much exclusively.
I always recommend dominions 3 by Illwinter to anyone who wants superb 4x, but there's so much more. One that really made 4x type stuff more accessible was Sins of a Solar Empire, check that out too.
Man, do I wish the historical stuff was more popular, though!