I'd like to throw out a suggestion to check out Anno 2070.

Tropico 3, (I guess 4 is pretty much the same just adds a few new things *shrug*. Not very futuristic though)

Those two games are, to me, pretty laid back games.

Already mentioned, but anyway:
Supreme Commander (the first one) is a very nice large-scale strategy game. Not something I'd want to play all the time, but every now and then, the scale and some of the experimental units are awesome to play with ;)
Imho the expansion is worth getting for the new race and improved balancing (though current patches for the main game will probably include the latter as well)

Dark Crusade and Soulstorm (expansions to the first Dawn of War game) are somewhat slower than Starcraft, I think, and use a basic version of the turn-based strategic campaign map. I really liked both and would recommend getting at least Dark Crusade. Soulstorm mainly adds two more races, not much change apart from that...

As you mentioned Empire at War: Did you use mods? I played quite a bit of Absolute Corruption, and thought it was vastly superior to the original game (plus expansion). Republic at War has been released recently as well, and it looks massive (including a long pdf manual with tons of pictures that looks really professional and is 500MB or something like that). I did not play it for more than 30min so far, but I'm sure it is awesome ;)
I would have preferred the strategic map in EaW to be turn-based, though... I ended up pausing the game all the time to make decisions.

Thanks a ton for the suggestions, folks.

I think I'll give Sins of a Solar Empire a shot. The scale and pace appeal to me right now.

Thank you!

Well there's what they call hard sci-fi and then there's pretty much everything that gets labelled sci-fi. I don't mind soft sci-fi getting labelled as sci-fi, even if it's not really all that fussed about scientific understanding. Not that all sci-fi has to be. Something like Fatherland could be called sci-fi as sci-fi covers alternate histories. It also covers taking existing socio-political situations to extremes, which alternative histories and future scenarios allow.

It could be argued that there is some evidence of this in 40K with the Empire being overtly totalitarian in nature.

But Games Workshop have stated this plainly that 40K is fantasy and not sci-fi. Even if you want to argue that the definition of sci-fi has been so diluted as to make inclusions like 40K possible, you can't really argue with the creators about their own creation.

The UFO series is always a nice sci fi semi-RTS for me. Squad-based and all that. It's here on GOG, but it's not everyone's thing. I like Aftershock the best, Afterlight is too dumbed-down for my taste.