UT99 + Nali Weapons 3.

Quake 1, Quake 3, UT '99, UT 2004, Zandronum (Doom 1/2 source port)

As for the other games, they either don't have multiplayer, or their multiplayer is a waste of time. Granted I haven't tried Unreal Tournament 3.

Another vote for Unreal.
UT 99, 2004 and even UT3 still have servers which you can join. But beware, most people online are pretty good as not much new blood is pouring into those games.

It also has by far the most competent bots which is what I play most of the time.

I remember playing UT 3 with this mod :

http://www.runestorm.com/ballistic

And add gore mod on which every kill will gib the enemies (I forgot which mod it was).

Even on singleplayer vs bot that's pure hectic fun!

Spent hundreds of hours playing that combo.

I played Unreal with a couple friends a few months ago. Sure, I had to set up my router to forward the correct ports, and tell them which domain to connect to, so, yeah, perhaps not what you mean by "online", but it definitely worked.

The Linux port (in the 227i patch) wouldn't run properly, so I had to run the Windows binary under Wine - that worked fine until it fucked up when I accidentally alt-tabbed out of the game so I had to restart it, thereby requiring them to re-connect. The expansion also isn't built for co-op, but we solved that with a mod and a couple admin commands.

Quake 2 with Chaos mod :D