I'm climbing the learning curve on Sins of a Solar Empire. It's been quite a while since I played any real time strategy games, but this one is shaping up to be pretty fun. It's got more depth than Starcraft, but seems pretty well balanced. PC Gamer loved it (editor's choice at about 91%, IIRC)
I haven't done a whole lot beyond familiarizing myself with the interface, but apparently the game can be won either by blowing stuff up or developing your culture to the point where they just surrender to you. The economy has a lot of depth. The tech tree is huge (game of the year edition came with a largish poster as a reference).
If you broke down in tears when Blizzard pushed the release date of Starcraft II out to 2010, this might be worth a look.