I'm not going to tell you which specific video card you should buy.
The following url might interrest you:
Information about supprted (video) chipsets for XFree (you are probably going to run KDE, Gnome or whatever windowmanager) etc etc.
Most (all??) of these will work with M$.