In an ideal world: Homeworld and Homeworld 2.

Though you may be lucky and manage to get copies on disc

The HD part is hardly a selling point, because modders gave AOE2 widescreen support long time ago.

What is a selling point is not to have use CDs for installation, new patches and online multiplayer.

Modders gave people that owned AOE2 HD support, but I did not own it, and it was a pain at times to find. Walmart sold it sometimes, but it was still a pain to find it, install it (using CD Keys), and then to mod it, while it still technically needed the CD in to play.

I could not figure out Defcon. So don't rely on me in a nuclear war.

I won AI War from a giveaway here and played it briefly. I definitely plan on picking it up later when it can be my one game I'm concentrating on, b/c it's a bit thick and highly strategic. It looks like a great game, but not a good starter.

I haven't tried Men of War yet.

If you want to try classics, tons of people have recommended good ones. Age of Empires laid a great framework for other games like it (AoE2 and 3, Empire Earths, Rise of Nations -- I recommend them all).

Each game has its own flavor and its own strengths. What I like to do is emerse myself in the simulation while playing. I don't care about making my brain and hand the master of the game. So I tend to stay away from ultra-competitive games such as StarCraft because I've seen people type through that game faster than I can type a paper. I've played against people who completely swarmed me and destroyed me before I had just a few units set up. That's just not my play style.

My all-time favorites are:
(* denotes availability on GOG)

Empire Earth* -- The span of epochs you can reach is spectacular. I've had 8-hour multiplayer games on this bad boy. It's truly epic. Caveman to outer space.

Stronghold* -- This game more-or-less simulates medieval castle-building and town-defending more interestingly than any other game. I have no idea about the real-ness, but I love the complex strategies of food management and forcing to keep some assets vulnerable while heavily defending others.

Rise of Nations -- Similar to Empire Earth, but not as many epochs nor takes as long to play. But the gameplay is, in my opinion, superior to any other RTS I've ever played.

Star Wars: Empire At War -- It's the best Star Wars one, though it's not the best game in the world. I really enjoyed it, though.

Star Trek Armada 1 and 2 -- both are stellar games. If you like Star Trek, it's icing on the cake.

Company of Heroes -- this is probably my favorite RTS for small-scale territory conquering. You don't deal with 500 units, you deal with a small few and use them to their utmost. It's highly competitive, but it's easy to find people close to your ability using their ranking system.

Why settle on RTS? Total war :), Lords of the realm 2. These have both.
I've also liked Starcraft, but also The Star Trek Armada games.
From here I'd recommend Cossacs, Empire Earth and Seven Kingdoms.

Someone needs to post a nice picture with a chart of games. Start Here, then move to this or this, from this go to this, or from that go to this...

Another vote against Men of war. While the game is good, it IS hard and very micromanagement oriented. Each unit has its own inventory and they even run out of ammo! You also don't have an economy aspect (like mining gold or minerals). It's very tactics oriented, more than your average RTS.

If you don't mind graphics, i'd go for original Starcraft. The campaign is good, it has an entertaining story, gives you a new unit to play with every mission and it's beatable all the way to the final mission. I never finished Brood War though (the expansion), the last couple of missions let me know my limits.

I also found Dawn of War to have a beatable campaign and it was on sale on the THQ bundle, so I don't know if you got your hands on that.

I know for sure that Company of Heroes can be paused, to the point you can give some commands and unpause it, if the game ever gets too hectic for you.

These three are all classic RTS games, a good way to start and find out if you have the itch for them.

I'm a complete noob when it comes to RTS and one game I had so much fun with was Age of Mythology Gold Edition. That's a fairly easy RTS that still feel modern when it comes to gameplay. Another good buy would be C & C First Decade/Complete Edition since that will give you all of the Command & Conquer games.

I forgot about Dawn of War, tho I have only really played 2, not Building based at all, but insanely fun Multiplayer. DOW 2 has some higher system requirements (comparatively), I have a GTS 450 1GB Edition, OC'd to 822 MHz and I struggle at Ultra, but I'm more than fine at High., but can be played on low settings as well.

don't go older than Warcraft 2, most of those games don't support right click and group selecting which is a pain (although, if you didn't play any RTS before you might survive it as you're not spoilt yet :)

the RTS games I've enjoyed the most in my RTS beginnings were Warcraft 2, Original War and Command & Conquer: Red Alert

I wouldn't recommend StarCraft as it is too hard for a beginner I think...

Yeah, the first one actually had a fair amount of base building (which actually came as a surprise, kinda, as Relic had emphasized many times before release that the game would be about combat and base building would play a minor role but ultimately base building had pretty much classic RTS relevance, arguably even more as you needed to build generators for one of the two resources). Anyway, I've played both and I prefer DoW1 by far. I just can't stand the amount of micro management in the second one and I love how huge and at the same time fast-paced DoW1 was. Also the single player campaigns are much more enjoyable in DoW1, IMHO, with most mechanics from multiplayer intact and especially the campaigns of Dark Crusade and Soul Storm mainly being a series of skirmish battles with a nice metagame attached (including a hero with unlockable gear and tough unlockable veteran squads which you can use as soon as the battle starts).

Also the plots of all DoW1 campaigns were much more enjoyable than what I've seen of DoW2 so far (I've only beaten the base campaign there) with a very cool and at times humorous approach. DoW2 had a much deeper plot with much more dialogue in the style of Star Craft but frankly I preferred those short simple cutscenes from DoW1 which captured the spirit of the Warhammer 40k universe with a few over the top lines (although I can't say that I didn't get goose bumps during the last sequence of DoW2 - seriously, that was one of the most amazing moments I've ever seen in a video game :D).

If you want to get started with RTS I recommend you start with the second game in the classics series. These are good and have decent interface and controls in their second games. Other RTS are usually variants on their core RTS genre mechanics.
These are the classics I can think of.

Age of Empires
Command & Conquer
StarCraft (It's ok to start with the first.)
WarCraft

Men of War is too micro intensive for a RTS beginner so I'd say wait with that.
Dawn of War and Company of Heroes WILL completely humiliate you even against the easiest AI until you have got some training with RTS games. Both are very good and fun. I wouldn't recommend a first time RTS player to them though. :P

Another good RTS is Sins of a Solar Empire. Forget what genre it's called because the gameplay is basically RTS.

Since you're a TBS player I think you'll like the Kohan games. Kohan: Immortal Sovereigns and Kohan: Ahriman's Gift are both good ones to start with. Kohan 2 plays much more like a standard RTS.
The Kohan games have a unique RTS gameplay which TBS players usually find very appealing. It's also much slower (Unless you get into a massive war with lots of companies on either side. That can get very stressful. :) ) and put much weight on you having a good economy and good troop composition.

I most certainly endorse Warcraft 2. I first played it in 1996 and it's still one of the two best games I've ever played (along with Planescape: Torment). I also suggest getting Command & Conquer: the First Decade. It's cheap and includes the first five C&C games (not counting Renegade, which is also included but is an FPS) and their expansions.

Men of War ... As his first RTS. Seriously, what did the guy do to you?

:D There is a lot of micromanagement in Men of War series, it's definitely not suitable for the beginners...