The answer (as it has been for quite some time; please search) will be:
Your best bet new is probably a RADEON 9600 (not the 9600SE, just the regular 9600), or a 9600Pro/XT if you can find one that cheap.
However, your best bang/buck is likely to be a used GeForce4Ti 4200/4600. Another option would be a used RADEON 9500Pro, or (if you are willing to spend a little more for a lot more performance), a used RADEON 9700Pro or 9800 (again, not the 9800SE, just the regular 9800).
Edit: This assumes you want AGP. If you want PCIe, ddviper has posted a pretty good link above.