www.wesnoth.org
It's turn-based fantasy warfare, but done far better (IMO) than Heroes of Might and Magic or even the various Civ-based games, which generally bog down into a little too much administrative work for my taste.
The game has a lot of scenarios and campaigns, in which the hook is a decent narrative, but the unit details are pretty extensive (each unit rated for move, HP, XP cost to "level up", types of ranged/melee attack, defense in various terrains and resistance to different types of attack) and you get quite attached to your "veterans" as you work through the various scenarios. There are a wide variety of units to fight with and against, and many of the tactical situations are pretty interesting (though that depends on the quality of the scenarios/campaigns).
As you might expect in this day and age, though, the game really comes alive online with the game server. There are all sorts of co-operative and competitive scenarios to play with people, and even a "ladder" to compete in and so forth.
Try it out! And look for "steve2" or "steveagain" on the server! is rocking my world.