I recently found an awesome free, open source first person shooter, AssaultCube — that has builds available for multiple operating systems including linux. Also, an assaultcube server is now up and running — accessible from ac.qrxx.com.
New: Check the status of the server here.
Update: Server temporarily taken down.
Update: Server taken down permanently.