Starcraft is a very fun mechanics-heavy Real Time Strategy. The universe is basically a clever rip-off/combo of many beloved sci-fi franchises, and the tech trees and gameplay aren't very hard to learn, just hard to master.
The competitive scene is also thriving, and the custom maps are incredible though they kind of struggle along compared to how dominant they were with Brood War. Some of the Arcade (custom) maps made by regular folks are my all-time favorites. It's a nice break if you get tired of the constant multiplayer ladder play.
Starcraft 2's campaign is also excellent, though the biggest gripe a lot of people have is that it has a lot of units and tech that isn't in the multiplayer. In spite of this, the multi has plenty of things to help you learn how to play at a solid, competitive level, and the league system is fairly solid.
---
For historical, you can't go wrong with Medieval 2. In my and many others opinions, it's the absolute best of the Total War series. New enough for decent graphics and old enough not to suffer from the dumbing-down and stripping of some of the newer entries in the series (cough Rome 2 cough.)
Strategy games have a long and colorful history, so if you're willing to play older games, there's an entire library of excellent titles, real-time and turn-based. A lot of the better fantasy games are older, like Warcraft 2, Age of Wonders, Myth: The Fallen Lords, etc...
The Civilization games are, of course, legendary themselves, but they have a bigger scope and lack real-time tactical combat.