A List of The Best Native Linux Games I've Found

I use Ubuntu Hardy Heron 8.04 so I wouldn't know about other distros.
When I say "Native" Linux games, I mean they were designed or compiled from source to run on Linux without emulation.
Getting down to business: Each entry will be the link to the corresponding website where you can download these games. I wont list games you can't download and play for free.

• Quake 4 For Linux *.run Packages FTP Downloads
  Torrent Download For the Current Version
  Documentation / Installation Instructions
  Technically, it's not free but it's a very good example that Linux can definately be used for gaming commercially.
  
• PlayDeb.net - This website maintains a list of games specifically converted/compiled to be easily installed on Ubuntu Linux by way of *.Deb packages.
• Urban Terror - This Counter-Strike clone is actually very good. It's not setup the exact same way, but you can still choose your appearance, good guys or bad guys, different weapons, etc. The maps and graphics are well done. There are also a lot of players and servers in the server browser too.
• Tremulous - If you've ever played a mod for Half-Life a while ago before it went Source, there was a mod called "Natural Selection"... Anyway, this game is somewhat similar in the aspect of FPS/RTS gaming. It has excellent graphics and it's free!
• Cube 2: Sauerbraten - No, it's not a German website, it's all written in English. Ok, this one is interesting; it has superb graphics, awesome in-game map editing, and the game engine it uses is entirely original in code and design. Best of all, and my focus of interest here, The Game Engine is Open Source, which means, with some programming knowledge, you can use it to make your own game with! Refer to their terms and licencing to make sure you're allowed to release as commercial projects, etc.
• Warsow - This is a basic deathmatch FPS with somewhat arcade/futuristic style graphics with some cell-shading effects. Nice graphics, fun game.
• Wolfenstein: Enemy Territory - Probably the most widely known free, high quality Native Linux FPS out there. Tons of servers and active players online at all times, from all over the world. The graphics are excellent, there are tons of voices and other ambient effects, the controls are familiar, but best of all, aside from choosing one side or another, you choose character class, which decides what kinds of guns you get and your job on the field. For example: Engineers build structural objects along the map to advance spawn points and eventually capture the entire map and win the round. Very fun and customizable. This game supports many mods as well.
• PlaneShift - This is an MMORPG (Massively Multiplayer Online Role Playing Game) available for Windows, Linux and Mac OSX. The graphics are nice, the community is very friendly and welcoming, and the game is pretty solid. There tends to be a large base of RPers (Role Players), so if that's not your cup of tea, they wont bite or anything... All in all, another gem for Linux.

So, aside from those, there are more but I haven't tried them. There are a good deal of Windows games that will run using Wine, but don't expect any miracles.

Any game that uses Java or Flash or embeds in a webpage is also available on any operating system that supports the runtimes and plugins required by the game (Such as Java and Flash).

By The Way, there are a lot of emulators compiled for Linux and some you will recognize.

• NES - FCE Ultra / GFCEU (Gnome FCE Ultra Front-End)

• SNES - ZSNES (My favorite SNES emulator)

And others, but I haven't tried or installed them yet so I can't tell you if they work or not.
Actually, if you are playing an emulator, you might want to play those games with a controller/gamepad/joystick... Here's how I got mine to work with a nice GUI-Based app for ease of use.