Battle of Wesnoth - been there, seen it, got the scars

If you're fan of turn-based hexagon strategies you'll have to check this one out: Game is set in fantasy world so you can command dwarves, elves, undead and of course human troops (much like the classic game fantasy general), not to mention you've got opportunity to hook up with extremely attractive princess (you have to fight her several times before :). Rules are pretty complex, yet easy to understand - every kind of terrain has different defense modifiers and movement penalties. Units have different types of attacks and different vulnerabilities. For example skeletons are vulnerable to blunt and holy damage while they are pretty hard to harm in any other way, elevens gets defense bonuses when ending their turn in forest, mounted units can do double damage when charging (but then they also take double damage from retaliation strike) etc. What is really great about this game is changing of night and day - chaotic units such as undead or robbers are strongest in the night, while lawful units are strongest in bright day, so you have to plan ahead - attacking undead fort in deep night is nearly suicidemission even for experienced veteran units, while taking them down in bright day is a piece of cake. Also for a game made by community (so it is totally free - really) it has got really good graphics & music background.