I would opt for Warlords Battlecry 2. While the third installment has a better story mode I'm still angry with the devs for reducing the complexity of heroes leveling system. I really love it from the first games and it was something tht made it unique when compared to other RTS games from that era.

I'm surprised nobody mentioned Wargame: European Escalation yet.

I think it's a great, semi-realistic RTS with very good graphics. It has nice single player campaigns and multiplayer is fun too. Unfortunately it seems to be rather unpopular on GOG, which means chances of the even better successors getting released here are slim. You could vote for them on the wishlist though ;-)
Wargame: Airland Battle
Wargame Red Dragon

Well, does it feel much different to the third in terms of visuals and such? I'd be happy to try the second if it's indeed better.

The main reason I bought it is because much like Masters of Orion 3 - it was the only game I had played from the series, so it's the 'best' to my knowledge.

Pretty easy question.

Evil Genius - Strategy, Real Time.

I would say there are two main differences between Warlords Battlecry 2 and 3
- aforementioned hero levelling system (much better in 2)
- campaign (3 is story oriented while in 2 you start with a single province and you have to conquer everything so it's all about war without story)
Other differences are rather minor like there are more possible races in WB3.

I strongly recommend playing WB2 if you like levelling yor hero. Be sure to study hero upgrade tree and spells list first to know what you should do.

For a traditional RTS experience I think Galactic Battlegrounds, it's just a re skinned AoK (though not quite as good, I think the addition of flyers some what complicates the game) and AoK is one of the best RTS of all time.

For something less traditional, either of the Dungeon Keeper games or Populous the Beginning. Both are unique and interesting takes on the genre.

Total Annihilation is also a great game.

^ what he said, that pretty much covers it. Don't forget World in Conflict which is different and well done in its own right.

Seconded. I'd also recommend Men of War (inc Red Tide), Earth 2150 and World in Conflict. Wargame isn't bad either.

I haven't listed any tactical games in this, can do if desired.

Looks really cool. I'll inevitably get both one of these days. I love the 90s PC game intros, they just don't make them like that anymore.

Empire Earth and Stronghold are two games that I loved back in the day. I loved EE a lot more than Age of Empires.

Yep, Perimeter is one of those hidden gems not many people know about.

I'm a big fan of Stronghold. Building your economy is as much fun as the battles. Not as big a fan of Stronghold: Crusader.

I find that the fun of the standard Stronghold games (Stronghold and Stronghold 2) tends to be reveling in the medieval and parody atmosphere (not enough parody for the whole setting to be one, far too much Monty Python to be ignored). The siege mode is fun in both (Stronghold is a better game in every way) and the economic campaign is good in Stronghold 2 (in a way, I couldn't get very far in it). Castle builder is the only real way for me to play Stronghold 2 (Stronghold wins out with a good regular campaign, but its castle builder is also really good) as any time I try any other mode it ends quickly and badly. It's fun to get a fully functioning castle and economy running especially with all the extra buildings they added (gong was annoying until it got funny and after adding the collectors it was a non event).

I really like Crusader for the standard game and the campaigns. The economy isn't as fun to play with here but in this game it's one of the few times that tension actually adds to the experience. People dog on it for good reason but I enjoy Stronghold Legends a lot. It got me into the Arthurian romance/legend as well as the Germanic legends and for that I shall always be grateful, but even with that I thought that the Arthur campaign was actually fun and I enjoy the standard game in that as well.

Empire Earth 1 is just gold, perfect game. I remember when I was still in college me and friends would play custom maps with unlimited resources, we'd start at Caveman and go right to Nano, but instead of just fighting we'd kinda roleplay it, like engage in diplomacy, have our own borders, engage in alliances and deals (they're was like 7 or us).
We'd be pretty much playing the same map all day.

Yes indeed. I doubt that any person that isn't a real hardcore rts fan ever heard of Perimeter.