Depends on how much you really want to spend. I cant speak for ATI cards because im a fan of Nvidia, but if you dont want to spend to much you can go with the GeForce 8800 GT Video Card which is about $200, or the or just go all out with an 8800 Ultra.
But those are about the fastest you will get.
Unfortunately, you're not looking at any real blistering graphics here. I'd recommend one of the HD2400PRO cards. In my experience ATI does a better job with lower-end graphics cards and provides better support to them than nVidia does. I'd recommend reading the reviews from newegg and deciding based on that. My guess is that the regulars on this site won't have too much experience shopping for these.
Your probably right. Most people here built their systems up to run Vista at its best. I personally wouldnt go with anything but the best to make sure my system ran great.
I dont mind the random problems that occur with Vista like the memory problem with 4 gigs installed and a high end graphics card with something like 768 mb of ram. Sometimes it can be a challenge to fix it and get it right but in the end it pays off.