Short bio: Computer Scientist, FOSS supporter (read more)
Tux Machines (TM)-specific
After recommending those excellent real-time strategy (RTS) games for Linux, let's move on to this other type of strategic gaming referred to as turn-based. A game is considered turn-based if the game flow is divided into well-defined and visible parts, called turns or rounds. Turn-based Strategy (TBS) games may be less action-packed than RTS, but they are more mentally challenging. --A player of a turn-based game is allowed a period of analysis (sometimes bounded, sometimes unbounded) before committing to a game action, ensuring a separation between the game flow and the thinking process.
If you are already bored of playing chess, how about trying these highly entertaining and challenging free and open-source turn-based strategy games that you can easily get and install on Linux:
The Battle for Wesnoth
The Battle for Wesnoth, or simply Wesnoth, is based on the Sega Genesis games Master of Monsters and Warsong (also known as Langrisser). It is played on a hex map, with single-player campaigns as well as multi-player matches. A central philosophy in the design of the game is the KISS (Keep It Short and Simple) principle; for a new idea to be accepted, it should not complicate gameplay.
The Battle for Wesnoth is set in a fantasy environment, in which players build armies comprised of different units from races such as humans, elves, dwarves, orcs, trolls, and more. This includes many custom made races, as anyone can customize the game.