I second the nvidia fx5200 card. Its what I have its fantastic value for money. Its cheap but its capable of playing most games up to there medium settings. Im playing doom and unreal tournament 2004 with the medium graphics settings turned on and it works perfectly, not a problem what so ever.
Stick with nvidia rather then ati cards. They have better support for linux, release regular drivers and are much easier to install he drivers for then ati on any distribution.