Starcraft. It follows my favourite 'style' (not sure what else to call it) of difficulty: Easy to learn, hard to master. The story is almost Hollywood styled, and thus is terrible, but the missions are quite different in their goals and rather fun to play.
Each of the three races play completely differently, with different types of units for all three (Yes, they all have the basic light unit, then the basic heavy unit, but even these are rather different from each other)
The Terrans play the closest to most RTS races: Normal units have few active abilities, and their building style follows the classic 'tell worker to build, he builds, he sits around until you tell him what to do). They build all their units from buildings, and the only really special thing I'd say about them is their ability to lift of their building and fly it elsewhere. Oh, and they also have the only dedicated healer unit in the game (Yes, the Zerg queen can heal, but thats not its primary purpose)
The Protoss are the next most similar. They focus on fewer, specialised soldiers whilst having the most types of units of any race. They are arguably the weakest race at the start of the game, but if you make it to end-game: They are unstoppable. Their workers work differently to the Terran's: they place a building, then wait for you to tell them to do something else whilst the building builds itself. All units are built from buildings, but later in the game you can warp all infantry units to a power source (Pylon or deployed warp prism) instead of building them to get them instantly onto the field or build your army in an enemies base. (The units being warped are being built. It takes around 2-3 seconds to warp in, and has a cooldown for each unit. Good if you need an instant army though).
The Zerg play differently to any other race I have seen in RTSs. They focus on swarm tactics, using a lot of units to overwhelm the enemy, however, you need to have built the right units or else they will be annihilated (By the right units I mean counters to enemy units, not 'mass unit X to win'). Their workers are consumed in the process of building a building, but they only need one of each building anyway (excluding the main base, more than one is required for a fast return rate [one per base is fine. With the other buildings you can have one per game{so long as you replace it if it is destroyed}]). Units are not built by buildings. Instead, the buildings provide the technology for the units (upgrades are purchased from the building, but just having the building will allow you to build the unit. Not having one of the building will not let you build one of the unit), whilst automatically spawning (until a maximum of three, unless a queen is used) non-usable (except for making units) units morph into the unit type you choose. They also can only build on a substance known as creep that is spread from their main building, creep tumours created by a queen, and by overlords spewing it out.
Strategy falls into two categories: Micro and Macro
Micro involves using your units and their abilities to have a more efficient force on the battlefield. Tactics such as placing units on higher ground, moving low-health units back and having full health units 'tank', and having specialist units use their abilities at the right time and place are in this category, as is army movement and, to an extent, worker management (although a lot of this falls into macro).
Macro involves the building of you base, economy and army to maximise effectiveness. Tactics involving the number of workers to build, when to build them, what buildings to build and when to build them, and building units to counter your opponents fall into this category, as does resource management.
The game is fast paced, so most who haven't played it see it as either really simple, or really difficult (depending on whether they see the smaller tactics that go into playing, and not just the building of the units and using their abilities, there is far more to it then that). However, all that they are seeing of one of the two sides of the easy to learn, hard to master difficulty. You can pick up the game and play to win against easy and normal AIs in seconds, and the campaign on normal is an absolute cakewalk. However, if you want to play competitively at a high level (Multiplayer works in leagues, which you are placed in according to your skill level. The worst players are in bronze [or maybe they added copper, I'm not sure] whilst the best are in Diamond. The best of the best are in Master and Grandmaster leagues) or defeat insane AI, you WILL have to learn the more subtle gameplay mechanics.
I have not played any Dawn of War games, and thus cannot comment, but Starcraft 2 is absolutely amazing.
)
