I play Ur-Quan Masters, aka Star Control 2. I don’t play the long adventure/campaign/story stuff, I just play the Super Melee mode. The computer gets some ships, I get some ships, and we fight it out till one side is defeated. UQM is available for Linux through various distros.
I also play Tank Commander, a Battle-Zone-like game made for the GameBoy Advance. It’s my favorate GBA game, though sometimes it is a bit frustrating (three gold enemies in a row, and no shield upgrades?!) Tank Commander is a GBA home-brew, and a very fine one at that.