Mr.Tea said:
AGP or a PCI-Express slot? (In other words, what motherboard does it have?) If it's AGP, your upgrade path is seriously limited. Otherwise you could easily buy a new card many times as powerful for relatively small price. (Like a GeForce 9600 GT or a Radeon HD 3870)
The above is a major concern that would greatly help us determine what you need.
If you do have a PCI-E slot, anything nVidia in the 7000 series or greater (ending in 500+) and has more than 256MB of RAM will do you fine for a few years.
If you have Vista, you will need one with DirectX 10, nVidia cards in the 8000 series or greater (again ending with 500+).
As for AGP, well, it will be expensive to get anything current that runs through AGP.
I was able to get a 9500GT with 1GB of RAM for $40 on NewEgg, so video cards are not expensive.
Edit: Sorry to all the ATI fans, I've had too many nightmares with ATI cards to begin to mention (driver problems, multiple monitor problems, etc.)