If you don't own a rather current P4 or AMD system don't bother with the $500 video cards. With that said if you currently have a 64meg card and you upgraded to a low end mediocre 128 card, you may only see a small difference. If you get a decent 128 or 256 card though, the game especially in a FPS should run a bit crisper and look sharper. I mean have you ever clicked on graphics option on a FPS before? If you have a great system and a good 128/256 card you could have everything checked and the game would still run fast and look great. Those screenshots you see on game box covers...they weren't off a mediocre video card that's for sure.
The answer to your question depends on the game you are playing. This site will have all the info you need, and can better answer any specific questions that you'll likely have. Read their forums.
Most of the info is trustworthy, but beware the ATI / nVidia wars. Pay attention to what equipment the gurus are using, and go from there.
My gaming system currently uses an Excalibur ATI Radeon 9800Pro "IceQ" card from HIS, noted for its unique cooling system and overclocking abilities. I paid a little over $200 a couple of months ago. There are cheaper and much more expensive cards, and there are much faster and much slower cards. This was the card that met my needs, and I couldn't be happier with it. You'll have to pay close to that to get a really good card, but the price range you were told is correct. Expect to spend $100 for an entry level gaming card, and $500 for the latest and greatest top end card. Last year's top end cards go for $200-250, which is the direction I went.
YChang speaks the truth regarding your other system specs. A new video card won't help much if the rest of your system isn't up to snuff. What do you have?
the 9800series from ATI and the 5900 ones from nvidia are going for real good prices now since X800/6800 are out.
i tried playing battlefield vietnam on my pc and it was waay too choppy (i have an mx440 128mb, which is a very low end card). memory isnt the only factor you should go by.