I never understood how come when you join a server there are guys that have memorized every key combination and every trick in the book to give them the edge, and this is probably not the only one they're playing either.
So here are a few options, including commercial ones. Staples of the free software world such as Wesnoth and Freeciv are not going to be mentioned because frankly, the graphics just suck. I'm also more of a FPS guy, but the same is true for Urban Terror and Assaultcube. Being multi-player shooters only the game play is also rather limited. Even Soldier of Fortune back in the day was more fun and still looks decent, and you're not gong to convince people Linux is a viable gaming platform offering them pre-1998 graphics or kiddie games like Blobwars or Frozenbubble (although that one was fun for a while). And who doesn't mind spending money on games for other platforms should not have a problem shelling some out for a Linux version. Most of the time you won't have to, though.
Games only running in Wine, however well, also don't qualify. Same for DOSBox, and although it offers a great retro feel and I really enjoyed Heretic again, more so than in a native Doom engine port, anything you could play in it is seriously old. Native or browser based is what we're looking for, although the latter may have to get a seperate post.
HEXEN: Edge of Chaos
This is an entirely fan driven modding project that is recreating the HeXen universe on top of the DooM 3 engine, so that game is needed in order to load the mod. It's a standalone game in itself and is not just skinning DooM 3. In January 2011 a playable Alpha featuring the first three levels was released. It's looking seriously good and if you like your shooters and that sort of ambience this can be nice time waster. The player can now climb up walls and ladders and you get some nice animation effects that were missing in HeXen II. Perhaps better wait until the
Also take a look at the Swamp level.
To play the above you need this, but it's also still a great title on its own and always worth a replay. Just have a look over on Youtube at all the mods available for it, from weapons, texture and lighting to fully blown campaigns, a coop mode called Last Man Standing and new maps. A long list is here, and there's more on PlanetDoom.
The most important thing I almost forgot is that there has been a x86 installer around practically as long as the game is in existence. It is not being updated anymore and no hopes of a x64 installer, but it still works. Several guides on how to install this are around in addition to the instructions on Zerowing, amongst them this one for Ubuntu.
If you invest in a copy of DooM 3 at the cost of around a fiver now you get a lot of bang for your buck with all the stuff out there that requires it. If you like hell on Mars you may even get the Resurrection of Evil expansion pack as well for a similar price.
Or how about the Raccoon City Chronicles (careful: loud music ahead) mod?
The Dark Mod
There have been plenty of fan missions for Thief I and Thief II, aided by the release of the level editor when Looking Glass Studios went down. Fan missions have also been created for Thief: Deadly Shadows, although less in number, and Thievery UT utilized Unreal Tournament to bring a multi player mode into the Thief universe. Unfortunately none of these ever had an installer released for Linux, possibly due to having opted for D3d with no OpenGL support? Just guessing.
This is another mod for DooM 3, aimed at recreating the atmosphere and environment of the Thief franchise with this engine. It allows the very active fan community to work with more modern tech, and once again have swimmable water which was notably absent in TDS.
The Dark Mod is a tool set to enable level creators to create their own missions, by default only a training mission is included. Apparently there are now over 45 missions available, as stated in this post announcing the latest five.
HeXen II: Hammer of Thyrion
If you like it gothic HeXen II and the expansion pack Portal of Praevus are a bit long in the tooth now, but graphics are still somewhat acceptable if you turn up glow effects and antialiasing.
Just as important, there is a Linux installer around created by a project called Hammer of Thyrion, both for x86 and x64. You can find more information and a download section here and here (read the features). You need the original game to copy the maps into the installer. Unfortunately there doesn't seem to be a similar project for Heretic II on Linux, although an old installer from Loki is around.
This project is truly cross-platform and brings plenty of enhancements to the original engine to the table, among them
OpenGL enhancements including multitexturing, glow effects, working brightness control, text and hud size changing on the fly, translucent console background, console background stretching, colored lights and support for external lit files, fixes for texture cache and model mesh cache mismatches.
And it's one of a few that let the player switch to first or third person according to preference.
Savage 2: A Tortured Soul
A cross-platform multi-player game that combines aspects of RPG and FPS, and the successor to the now dated looking Savage Newerth. It is all player vs. player, you choose a team and defend your base. Savage 2: A Tortured Soul is available for Linux in 32 and 64 bit binaries as a free download of a little over 800 MB. You run the .bin file to install, and can then join other players on Windows and Mac OS X (Intel only). Apparently it is rather heavy and to get all the glorious graphics requires a Quad core machine which could still pose a problem for some. At least enjoy the video.
Glest and MegaGlest
If you're an RTS fan this is for you. Glest is a free 3D real-time strategy game in the style of Age of Empires with a fantasy theme and also an engine and invites the creation of maps and mods. The Glest Mega pack adds more factions and creatures and players generally have to choose between magic or technology. The possibilities to mod this introducing more factions are virtually endless. MegaGlest forked in 2010, and one of them is almost certainly in the repositories of your distribution of choice.
There is also the Glest Advanced Engine community driven project which aims to extend and
improve on Glest to result in higher quality strategy games in the future.
ID Software has been a supporter of Linux on the gaming front from early on, that's why they are featured so heavily here. Linux installers may have come only after the release and are not bundled with the game but need an extra download, but at least they make them available at all, and it's easy enough to copy your maps over from the DVD. This installer again is 32 bit only.
Just like with DooM 3 the installer for Quake 4 can be downloaded from Zerowing and all the instructions are clearly set out. Still cool, and plenty of mods and maps available.
Alienarena 2011 is a huge update to the original Alienarena and is built on the Unreal 3 engine. From what I've seen it looks spectacular. Basically, it's a different game if I remember the rather bland Alienarena of old correctly. The latest version 7.51 is available for Linux as a 367 MB file and also via torrent. The official download seems 32 bit only, you simply extract the zipped file and the game will try and detect your video settings on launch. Most distributions probably provide it as well, and there is a 64 bit version in the Arch repository.
Another shooter that's having a major overhaul is Nexuiz which started originally as a Quake modification. Unfortunately it looks like the new Nexuiz will be a commercial game and only available on consoles. For everyone else there is still classic (read old) Nexuiz which is now in version 2.5. It is an arena shooter style game similar in look and feel to OpenArena and Unreal Tournament, indeed some of the maps are almost identical, but with more bling in my opinion and still extremely fast on modern hardware. Plenty of maps are available and you can also play against bots if not on a network. Nexuiz is in most distributions' repositories, but at 850 MB a rather hefty download. You pay for the bling I guess.
Several more installers for such main titles as Devastation and Aliens vs. Predator can be found here, although some are rated beta quality they appear to come from games that were sold by for instance Lokigames. I did not try any of these but chances are they're still working.