I would recommend games from the developers of Valve. Counter-Strike is a good game and you can opt for older versions of 1.6 (oldest), Condition Zero (new maps and models, but essentially the same thing), and Source (an updated Counter-Strike on the Half-Life 2 Source engine). Day of Defeat: Source was also an interesting game (there is the original Day of Defeat, but I've never really played it). Team Fortress Classic was very fun in it's day, but I would recommend Team Fortress 2 in it's place.
Not only that, but Valve also makes good singleplayer games too with the Half-Life series. I would recommend getting The Orange Box if you wish to play Half-Life 2, Half-Life 2: Episode 1, Half-Life 2: Episode 2, Portal, and Team Fortress 2. These are all good games, but you can get the separately if you wish. Getting the new singleplayer games should also make you able to download user created mods where you can get some interesting user created content.
Also, Turtle Rock Studios, who are working on Left 4 Dead, was recently aquired by Valve. Left 4 Dead is a zombie game where 4 players (AI or human) play in online co-op and try to make it through a scenario while the AI director looks at their progress and sends tons of undead uglies at them. Not only that, but there are also 5 (4 can be player controlled) boss zombies that can further hinder the players. This is another game to keep an eye on as more information comes out.