grape1829: Warlock: Master of the Arcane is out in a few days. It's supposedly a mix of Civ and Master of Magic. I haven't played the latter, but after playing the demo of this game, I can say it is definitely worth a look if you liked the Civ series at least.
errr Warlock isn't sci-fi and isn't RTS -- other than those two minor problems with the OP's request its a great suggestion (demo on Steam at present and its loads of fun for any turnbased fantasy RTS fans)
As for suggestions on a good RTS I'd say:
Dark Reign 2 - great little gem here; good visuals, base building, one of the best unit AI control setups ever. Story is decent as well and is told from two different viewpoints for the two different factions.
Supreme commander 2 - slightly different gameplay style to the first game in this series, but I personally like many of the changes (esp making the tech tree contain less redundant unit types). Not quite the same scale feeling as the first, but still good solid fun with large bases.
Rise of Legends - great fantasy/scifi mix RTS game with a very well written story. Game has a steam punk; mystical arabic and techo aztec armies and is a lot of fun. Base building is a little more basic and you won't be building walls or fortifications but the gameplay is very solid.
PS if you like building bases I strongly suggest looking at Stronghold and Stronghold Crusaders - they are the first games in the series but the best (the 2nd kind of ties but fails and the 3rd outright fails). It is more historical based castle building - but you'll never get more fun in a game for building up castles and attacking opponent fortifications. Crusaders has a skirmish mode - the first game lacks this (though does have a free build mode and hitting F1 in that lets you summon invading armies.