I play Nexuiz as well and it is FANTASTIC. However, if you are used to console FPS, your in for a big surprise. Nexuiz is EXTREMELY fast. The best thing about it is it's speed & physics (which is why I will NOT be playing Xonotic). A good way to pick up quickly is to join a server (preferably House of CTF) and "spectate" one of the better players for a little while. This will show you the best way to move around and different tricks. Have fun and don't give up. :)
Also, another game (not free) that has a native Linux version is Eschalon (http://basiliskgames.com/). These are slower Diablo-esque games, but are really good and at a decent price.
Another good option, especially for old-school gamers is any kind of MUD. I play Ansalon (a Dragonlance MUD) and I really enjoy it. Gnome-Mud is a good program to play these and is in the repositories.