..upgrade it first...Adding the 2 X 512 MB would help substantially. Probably more than the video card upgrade..The card you have isn't bad, has a fair amount of it's own memory, and the upgrade may not help as much as the increase of overall system RAM. That may be the cheapest option to get a little more life out of your machine. Still, you have a number of options.
In my opinion, you're now asking for a gaming computer and upgrading this depends on how much money you want to spend. It requires a different set up standards and you might start looking for a new machine. If you're like many of us, you want to go as cheap as possible.
For example, watching our local advertisements, I'm seeing lot of AMD 64 machines and Pentium 4's going for very little money. (I recently helped my boss purchase an HP with a P4 3.0 GHZ, Dual-layer DVD drive, 120 GB HD, with 512 MB of RAM for $550. Although it had onboard graphics, it also had a PCI Express slot in it. If you added a graphics card and kicked up the RAM, then you'd probably have a decent gaming machine for around $700.) I'm sure you could find something cheaper than this as I've seen fairly decent processors going for less money than the computer example I gave.
Still, it's up to you...
Hope this helps.