The Battle for Wesnoth is a Free, turn-based tactical strategy game with a high fantasy theme, featuring both single-player, and online/hotseat multiplayer combat. Fight a desperate battle to reclaim the throne of Wesnoth, or take hand in any number of other adventures. Easily modifiable. You can even download other users' add-ons from the main menu.
Very fun Turn based strategy. I've heard some people complain about randomness but its very controlled and can be planned around. It is also completely open source and has a map editor packaged with it. There are mods people have built to take out randomness too if that's your fancy.
This was one of the first free games I ever played, and it's easily the best turn-based strategy game I've ever played!
The story is obviously thought-out, the graphics are clean and well-done, the music is amazing, and the free online play is a huge bonus!