I used to love RTS games and play them multi player a lot, but mainly I played multi-player because I finished the campaign and didn't find the AI challenging. Also the big problem with multi-player is the inevitable cheating. I loved C&C Generals, but the cheating just killed it. I remember it got so bad that people would pop down super weapons in the first 2 minutes of the game.
As far as the single player stuff, I do like a good story, but this seems to be really hard to do.
As far as general rts mechanics, I like truly different factions that each have many kinds of strategies. I do not mean simple stuff like air power vs ground vs navy, but more complex tactics, think of the Terran tank push from starcraft.
I also want my troops and formations to be smart (I hate micro managing stuff). IE: If you have selected a bunch of weaker ranged units like archers and you also have a bunch of swordsmen units, the archers will not run ahead of the swordsmen and then get trapped in melee. The archers will automatically form up behind the melee dudes.
I also like interesting techs and toys to play with. Techs that give you like 10% more damage are boring. Techs, like the GPS scrambler from C&C Generals Zero hour that permanently affected units in an AOE and made them invisible was cool. Another interesting tech in some game I played is that some tanks gained the ability to cloak and appear like normal trees and were essentially invisible while stationary. If they leveled up, they would also remain stealthed while firing.
Speaking of leveling up, I do like this as long as it is really meaningful. If units die quickly so that leveling up isn't viable, then this mechanic is a waste. Also if the level up is just a tiny statistical improvement, it is also pointless. Again I prefer new abilities, like the unit regenerates, move twice as fast, does double damage, etc. along with smaller statistical improvements like more HP, armor and longer range.
Lastly, the factions need to be interesting to play. I do not know if I have lost my taste for RTS games, but since generals and zero hour, I have not found a new RTS that has really grabbed me. Perhaps they have all been somewhat generic and bland although if I could see myself playing a remade version of C&C generals zero hour if there was no cheating in multi player.