I'll recommend you two options:
1) MechCommander 1 (Preferably 'Gold') or 2
2) Homeworld, Homeworld: Cataclysm, or perhaps Homeworld 2
Those are simply (IMO at least) the best RTS games available, period. They all share persistent units, so instead of the "build a horde and rush" mentality that Warcraft/Starcraft type games revolve upon, you have to carefully choose your unit composition and try to conserve them, as every unit lost is one less you'll have next mission. Heck, MechCommander even adds pilot skill and damage to the mix.
The MC games take place in the Battletech universe(more info
here); you command a company of battlemechs (8-to-12 meter tall bipedal war machines) in various sorties. In MC1 you're part of a regular army, but MC2's unit is a mercenary outfit, so you have to outfit yourself as best you can.
Homeworld is just a classic. It's a truly three-dimensional space-based RTS; instead of infantry and tanks you control a fleet composed of scout and interceptor fighters, attack bombers, frigates, destroyers, and your Mothership. The backstory, plot, and art style are simply superb, and gameplay is downright addicting (but in a good way). Relic even managed to weave in biblical references and overtones that seamlessly mesh with the overall tone of the game.
I haven't played Cataclysm and have only played HW2's demo, so I don't feel I can comment on them. However, I will say that HW2 is downright
gorgeous even on my no-longer-SOTA rig (1ghz, GeForce 2 MX, 512mb) with most of the extras turned down or off. Homeworld (1) does show its' age (1999) in the individual ship models, but the overall effect of a fleet engagement is still awe-inspiring.
My sig is a screencap from HW2 incidentally; those are the new-style interceptors (much purdier than HW1's).