One of the best fps-games in Linux is in my mind Urban Terror.
Its gots not the best graphics in the world but its ok and not like sticking forks in your eyes. What it does got is excellent movement and weapons balance. I like it that you can reach almost anything and gain an upper hand just by learning to move right so its not all about point and shoot but also about strategy and movement. I also appriciate that its not a fragfest like nexuiz or quake where its all about shooting all around you and guess where people will stand most of the time on small maps.
If you havent tried it i recommend it for anyone into fps games.
I play mainly on the Ubu Dumbers server so why not come along and get spanked?