Memory means almost nothing when it comes to graphic cards unless you want a super high resolution.
Go to newegg.com
Then pick one of these: Nvidia 8800 GT, Ati 4500, or Ati 4700.
Those are going from least powerful to most powerful.
If you wanna go really cheap you could get a Nvidia 8600 , now with this there is no reason to get above 256mb.