Starcraft: Brood War takes first place by miles. Not because it's particularly realistic, or because all that matters is your strategic skill - these are both manifestly untrue - but because of the sheer depth and variety of strategy and tactics involved. Remind me to tell you all about the Royal Stove sometime as a cautionary tale for overly complex plans.
Civilization IV (I play Beyond the Sword personally, but nothing's wrong with vanilla or Warlords) is also incredibly fun, for basically the same reason Starcraft is - complexity. Unfortunately, in Civ4 the complexity is in the rules, not what you can do with them, so it's slightly less timeless.
DotA, or Defense of the Ancients, a Warcraft III custom map (there's a thread in this very forum about Heroes of Newerth, a clone with better graphics and no competitive balance at all, so clearly some of you are at least vaguely familiar) is also pretty interesting strategically, if you're playing at a high enough level. The ban/pick system alone is a pretty entertaining strategy game, and that's just the beginning.
Finally, no post on strategy games would be complete without Allegiance, which is indescribably awesome. It's kinda-sorta a first person shooter, and kinda-sorta a space combat sim, but mostly it's a strategy game.
Never mind, that wasn't finally at all! Fooled you, didn't I? If you're willing to tolerate month upon month of extreme boredom and no free time for it (I'm not, but maybe you're more masochistic than me), upper-level "0.0" (pure player versus player) EVE Online play is a rather shockingly realistic simulation of large-scale space warfare.
And finally for real this time, we get to the one board game that makes this list - Diplomacy. Compared to the above, the mechanics are mind-bogglingly simple, but it's an excellent place to practice dealing with one's opponents - literally, making deals with them - in its purest form.