I'm about to upgrade my system as well, and I was planning on using my current video card (Matrox Millenium, 4MB) until I was able to do a little research on cards so see what's good (and what has drivers for *nix).
I've been using
http://www.pricewatch.com to find good prices, but this has gotten a little annoying, because much of the time you have to jump through hoops to get the listed vendor to honour the price. There's a bit of bait & switch too (oh, the advertised price is minus the heat sink and fan, even though all our other chip prices include that), and sometimes you are also limited to only one (quantity) of the advertised items.
I hope to be upgrading my system in the next month or so. The really funny thing is that I only need the upgrade because of Windows. FreeBSD still flies on my old P200 :P I'm just sick of waiting 2 years for NT4 to boot up, and like Josh, I have a game that needs Windows, and it's suffering bad from lack of CPU speed.
-Paul