Openarena is one of my favorite games for Linux. I cant believe I havnt shared it on this site yet, if you like fps games definitely check this game out!
OpenArena is a violent, sexy, multiplayer first person shooter based on the ioquake3 fork of the id tech 3 engine. It has many game types beyond deathmatch and a lot of characters. Due to violent and racy content, it may not be suitable for children under 17.
Openarena wiki, tweaks & other info!
If you got an extra machine with extra bandwidth you may want to consider contributing a gaming server to the openarena community, you can find more information on that here