Well, it's obvious that I'm not going to list all the video games. This is mainly a list to get you started on your way to gaming on Linux. I'm also assuming that you have taken a look at the games that came with your Linux distribution. Some of the common ones are also mentioned here, if they are truly stand out games.
There are several websites whose mission is to list and help you find Linux games. Here is a (no means complete) list of them.
Well, there used to be a company, Loki Software that made its money from porting well known Windows titles to Linux. Unfortunately, they didn't make it, and had to close. There are those who take this as a sign that the golden age is over for Linux gaming. Bah! I say to them. There are many games for Linux that are ingenious and good. Also, with things like WineX, if you just have to get that Windows game, there's a fair chance it will work.
All twitch, no think. These games are the kill or be killed sort.
A mutiplayer tank game, with 'flags' that embody power ups. Now has three modes of play, deathmatch, Capture the Flag, and "Rabbit" mode where you hunt the highest scoring person. Trilug runs a server for BZFlag at bzflag.trilug.org port 5154. Website: http://www.bzflag.org/
OpenGL Tron Light-Cycle game. Has network multi-player support, and some people have made skin packs for it that make it look just like the movie. Website: http://gltron.sourceforge.net/
Quake, the latest version. A pretty good shoot 'em up. http://www.idsoftware.com/
Unreal is another 3D shoot'em up. Arguably prettier and more fun that Quake 3, though each has it's loyal following. http://www.unrealtournament2004.com/
The Open Racing Car Simulator. A driving simulation for Linux and Windows that runs on OpenGL. You can make your own cars/tracks/AI's to drive the cars. Works with steering wheels and joysticks. http://torcs.sourceforge.net/
Arguably the primary reason for the Wine Project in the first place :) Half-Life under WineX works almost as well as under windows. Half-Life is one of the first action games to feature a "nerd" (actually a theoretical physicist) as the protagonist. Puts in the role of being a ground zero of an experiment in a top-secret research facility when something goes wrong. http://www.sierra.com/games/half-life/
These are the think-a-lot games. Usually simulations of some conflict or large process. Usually are very steep to learn, and take a lot of time to play. But can be amazingly soul-suckingly addictive.
The OSS version of Civilization, the strategy game where you guide your civilization through all of recorded history, building cities, discovering technologies, and waging war. FreeCiv stands out from its commercial competition with it's network play support, as well as user designable tile-sets, and modifiable rule-sets. Almost all distributions install this as part of their games. http://www.freeciv.org/
Aside from being the main reason I nearly flunked Linear Algebra, the Civilization series of games has been one of the most entertaining/addictive/enduring strategy games. (Hence it's really quite good OSS version)
Turn based Fantasy genre Strategy game. Use your elves and other forces of light to defeat the evil orcs. Frequently updated, and in development. http://www.wesnoth.org
Like Tetris/jigsaw puzzles/other brain teasers.
This is a cute little take on Tetris, available from ChronicLogic. Commonly reffered to as "squishy tetris". http://www.chroniclogic.com/
Remember Lemmings? Well, this is just like that only with penguins. Horribly addictive. http://pingus.seul.org
If you've ever downloaded Snood for Windows, and endured the gator installation, and the horrible graphics and sound for the addictive gameplay... This is like that, only pretty, with good music, and still horribly addictive. If not for this game, Linux would be the world-dominant OS. :) http://www.frozen-bubble.org/
A puzzle game about using a marble to uncover matching pairs. Sort of a Marble Madness meets concentration with a little Sokoban for flavor. http://www.nongnu.org/enigma/
Games where you play in the game world as an avatar, usually concentrating more on quests and puzzles than killing things. Though there is usually plenty of killing things too.
Rogue is arguably one of the oldest computerized RPG games out there, and still amazingly fun. (The Diablo games are based entirely on it's mode of play.) The idea being that you are an adventurer in a dungeon battling monsters and collecting treasure, while searching for some goal. The dungeons are random, so no game is like any other. (Except that I always get killed before reaching level 10 of the dungeon)
There are many takes on this theme. Rogue is the first, Nethack is a more campy, arguably the most popular version. Angband is a more Tolkien themed version, Moria is another Tolkien based one. There are many others, for many OS's. http://www.win.tue.nl/~kroisos/roguelike.html
Falcon's Eye is an attempt to put Diablo like graphics onto Nethack. http://www.hut.fi/~jtpelto2/nethack.html
Uplink is an RPG that puts you in the role of a nascent hacker, in the year 2010. You are put in with very little info, other than that you just joined a groups called Uplink, and you can perform jobs for them, upgrade your computers, and even get arrested depending on how things go. http://www.introversion.co.uk/
The classic hack & slash. Very similar to Nethack/Rogue, with pretty graphics and sound. Can be run using WineX. Excellent graphics, good sound. http://www.blizzard.com/worlds-diablo.shtml
NWN is an on-line (Or single player) D&D game, there is an included campaign, but NWN comes with the tools to create your own campaign. Bioware has released a linux version of everything except the tools to create your own campaigns. Probably the best D&D computer game I've seen and thus really terrifically productivity killing. http://www.neverwinternights.com/