The Humble Store has a number of Linux games: http://pcgamingwiki.com/wiki/Humble_Store

Sid Meier's Alpha Centauri is a favourite of mine, not sure how easy it is to get a copy of these days though.

DEFCON, Darwinia: http://introversion.co.uk/

Wesnoth is a great turn-based strategy game and has an unusual amount of polish for a FOSS game.

SpringRTS is a really fun RTS, if you can look past the many bugs in the launcher/lobby: http://springrts.com/