My favourite on-line FPS is Natural Selection. Since it's a Half-Life mod it's cheap and doesn't need the latest hardware to run. So that's my suggestion.
ET is a nice alternative too, as it's free and available for both Windows and Linux, although demanding more from the hardware.
/Martin