I think you guys are picking far to complicated ones to start. I would recomend some of the oldies with one resource and simple rock paper scissors gameplay. Age of Empires: Wonderfull RTS, but not only do you resource manage food/rock/gold/timber, your work force is very important.. while i agree its a great learning one, I dont think its the best first one.
I would go back, the graphics are ugly but DUNE II (still my all time favorite, but pretty simple nowdays) or Warcraft. Dune II has one resource and really teachs how easy it is to be shut down if you cut off the resources. Warcraft adds 2 resources... Tis purely from a learning standpoint, the interface is clunky, the gameplay is simple.
I do agree, Starcraft may be the single best "overall" one to get a grasp on. It has almost ever thing that makes a RTS good, non mirror units, rock/paper/scissor. Always a counter to whatever the other guys does. learning to use different types of units instead of the "tank rushs" the early games where so famous for.
I think in the end the COH RTS is about the best "balance" and one of the most fun.
I cant imagine people who dont enjoy or play RTS's, they may be my favorite game genre. I think i have played almost every one made (many horrible ones, even more so-so ones and some good, and a couple great ones).
As for multi play, no amount of single play can prepare you for the smake down you will get in Multi. As somebody said, single play and multi are completely different. If you want to play multi you need to learn every Hotkey by heart, be able to manage units in the mini map as well as the full map, basicly you have to make two hands do what it should take 4 hands to do. Reaction time is important, unit makeup is important, build rate, build order, owning certian parts of maps at certian times, cutting off map, worker rushes, turtleing up, choke points, defence, offece.. and about 100 more things i forget. Once you get good at multi, single play is worthless

enjoy the dingle play days!