Lately I played Amnesia the dark Descent, which runs natively on Linux and will scare the heck out of you (it's a first person survival with no weapons, so not properly an FPS). Linux version costs around 15 euros and you will support both the developers and games on Linux by getting it
Sanctum is pretty fun too: it's a turret defense mod for Unreal (http://www.fileplanet.com/212714/210...o/Sanctum-Demo
), but I only played it on vista so I can't tell you whether it works or not on Linux.
UT2004, as they already told you, is a must but it might be hard to find it legally; otherwise you can give a look on gog.com (I guess older games tend to work better in Wine). I got Divine Divinity from there and it works like a charm but you can browse for FPS. Also Neverwinter Nights got ported if u like RPGs, but you should check if they provide the Linux version on gog.
Lately a friend told me about a game called Dark Horizons (but I don't know what kind of game it is): http://www.torquepowered.com/products/dhlore
- from the screens I'd say an FPS?
And lastly, give RUSE a try - it's a RTS really, but it works perfectly in Wine.
Or, if you can make them run on Linux: Deus Ex, Dead Space, Fear, Undying, American McGee's Alice, Borderlands.