SupCom is pretty good. I suck at RTSes, and the way skirmish is set up it's pretty easy to find something that challenges you- choose between (in the expansion) easy, normal, rush, tech, adaptive and turtle as well as an "AIx" version of each, which cheats if you're fighting off seven teamed adaptive AIs with ease. Or you can just set up a big map, with you and some easy AI ally meat shields, then add an enemy team made up of rush AIs. Even if you lose, it makes an awesome last stand against the on rushing horde.
DoW II would make a good intro to the genre, as it's more small scale than most, with no more than four units avaliable on any one mission (well, except one.)