A Savage4 served me well for a long time. The last driver update was about five months ago -keep in mind that it is a seasoned chipset with little need for further driver changes. Like every other viddy card you have to use the reference drivers from the chip manufacturer, not the branded outdated ones from the board maker. It is still used in current integrated chipsets. I call it venerable and frequently find myself defending it and repeating the same things.
I don't know about those games specifically but essentially the S4 plays the large majority of games in W9x fast 'n' purty at 800x600. For Half-Life, UT, Q3, etc. it is killer though with the newer cutting edge games the S4 does start to show its age.
I did not find anything worthy of replacing it with until the Geforce 2 MX. But given that it lacks features and quality and only just managed to get into the next resolution (1024) at 32 bit color it was not a clear decision (I was not willing to settle for just faster 800x600x32). I waited for TwinView to pan out and it never really did. Then along came the Radeon LE, which settled the major problem with the Radeon, being price. The next potential problem was the drivers and now that I have seen them for myself I would say they are not bad but do need improvement as far as maximizing the chip's speed potential, especially in W2K. But I find it really is more than fast enough to play everything in W9x trouble-free at 1024x768 or 1152x864 32bit which is the range my monitor is limited to anyway.
I think in the next few months the drivers will probably make the Radeon even better. If you want a replacement in this price range now I would recommend it. If you wait a bit more the rollout of the Geforce 3, Kryo II, Radeon II, etc will only make it cheaper but I have not heard of anything else promising unless you are willing to consider a Geforce 2 as they come down in price.