bitstream is right on target.
If your motherboard has an AGP slot, you can get a previous generation (but still, kick arse) video card quite cheap.
Among the cards listed by bitstream, GeForce2 GTS is, probably, the best choice (64MB RAM doesn't do any good to the slower MX chips).
I've got my GTS-V from www.newegg.com for $49. They don't have them in stock now, but you have to check them from time to time.
CPU speed doesn't matter as much as the video card. When I switched from ATI Rage128 card to GeForce2 GTS in the same 850MHz Celeron machine, my FPS increased ten-fold: from 5 to 50 FPS in 1280x1024 in 32-bit color!