I just played Nexuiz for the first time about 2 weeks ago, and I'm hooked. I was always hesitant because the screenshots didn't look too good. Now that I've played it, I like it more than Warsow and Alien Arena combined. It's a really fun game, and the graphics are much better than I anticipated.
The funny part is, I wouldn't have tried it had I not seen the YouTube videos of it.
Oh, and the best game on Linux is clearly Neverball