If you feel like trying something different with loads of different gameplay outcomes, you could try:
Earth 2150 (and it's standalone expansions "Lost Souls" and "The Moon Project")
Excellent storyline, huge tech tree, and completely custom-built units with highly detailed AI modes (not just aggressive and defensive, but also settings like "flee at x% health", "lights out" makes them less visible at night, platoons allow organised armies that really act as an army should...). Also the three playable factions are actually vastly different in terms of resource gathering, unit specialities and construction. Compared to them, Terrans, Protoss and Zerg seem like palette swaps.
Earth 2160 isn't bad either, but extremely dumbed down compared to 2150. Still a great storyline, though, and, like its predecessor, excellent voice acting (at least in German. It's an "old-European" production after all).
The War Of The Worlds (What I usually refer to when I say WoW, since it's much older than World Of Warcraft)
The best comparison might be the Total War series. You get a "world map" (actually an "England map"), where you move your units around, and at any time you can switch to local map view to build structures, and of course to fight battles.
BOth factions are completely different in terms of economy, research, military and of course design, and I never ever managed to complete every research item in one playthrough on either side. No (officially supported) multiplayer though. It's in the code, but hidden. Probably because a multiplayer game of that kindwould take ages.