I was looking into getting a more recent gfx card for my peecee a few weeks ago and concluded I should get a very low budget card (well my budget was very low :-)).
I went for a GeForce 4MX 440, I must say the picture is quite sucky. Dunno how much difference a cheapish Radeon would make, the cheapish OEM manufacturer of my card also might have something to do with it (Point of View). :-D.