Looking to upgrade - advice please

[Uncle Yuan]

Our newest computer, which ought to be fairly powerful, is pretty mediocre when it comes to games.  CoX can only be run on lower settings and Heroes of Might and Magic IV is painfully slow, although it looks great.

This is what I have:
Compaq Presario SR1750NX
2.19 GHz Athalon 64
"1 gig" RAM
ATI Radeon Xpress 200 video card

Processor I can't do much about.  I can easily (and inexpensively) double the RAM.

So basically, its the video card I am very unhappy with.  Any thoughts about what would be a solid, not wallet breaking video card to put in this?