How many players are you going to have? It\'s easy to say Quake / Tribes / Counter-Strike etc. are the greatest multiplayer games, but if you only have 2-3 players, they will suck for sure. Ok, maybe they won\'t suck, but you will get tired of them fast.
I think strategy games are a better choice for a small number of players, so you should consider the traditional ones like Red Alert / Starcraft. The one I would really recommend is Homeworld, which is VERY playable and enjoyable with as few as 2 players. Ground Control might be another good choice, but I don\'t like the fact that you can\'t control individual units.
BTW, if you can find an cheap copy of Activision\'s Battlezone (the version released in 1997), then get it. Deathmatch games in BZ are great with lots of players, but it also had a Strategy game mode that was fantastic with 2-4 players. Be advised there is a learning curve.