This one regularly gets rated as a top 10 linux game.
Check out the vendors forum release thread for more information.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.
from synaptic, enable the test repo and search for wesnoth-1.13. Everything but the music package gets checked so be sure to also check wesnoth-1.13-music. There are 2 older versions available 1.10 & 1.12.