It's a great time to be interested in strategy, there's so much choice out there, and *loads* more in development.
My personal ranking of the best strategy games I've played...
-Rome: Total War (basically combines Civilization's empire management with AoEesque RTS combat, though **vastly** better and more tactical than the latter)
-Sid Meier's Alpha Centauri (aged a *lot* now, and hideously ugly, but afaik it's one of a kind in being a story-driven turn-based-strategy. Basically Civ plus a few interesting elements such as the ability to design your own units, build sea colonies, very unique factions, a craft-your-own-government feature and of course advanced sci-fi)
-Civilization series (generally thought of as the pinnacle of turn-based strategy; build a civilisation from a bunch of settlers right up to a globe-spanning empire. 2 is the best in my opinion, especially as it runs in a window, 3 isn't much good, 4 is great but has something lacking)
-Dawn of War (ace sci-fi RTS set in the Warhammer 40k universe, very fast paced and frenetic. Kind of the UT of strategy games. ;P)
-Age of Empires series/Age of Mythology (used to be the benchmark for RTSs to be measured against, but the series has become very outdated and eclipsed by the Total War series. Still, if you prefer day-length battles instead of week-long conquests or hour-long blastathons then it's worth checking these out. The first two are the best in my opinion)
I've never really been attracted by C&C, but you should probably give those a try too...
As for online, I've never tried playing a strategy game over the net before, but apparently Dawn of War is great online, and Civ 4 was designed with it in mind, though from what I hear it can be rather buggy.