My computer isn't very different from yours. I have a G4 / 533 MHz with 640 MB of RAM. I upgraded to a GeForce4 MX with 64 MB of video memory.
It does quite well running dual screens and makes OS X more responsive thanks to Quartz Extreme. Having more RAM may be an important part of the difference as well, though it's not as big a deal if you don't leave too many apps open at once. In that respect, it kind of depends on how you use your computer.
The WarCraft III demo is definitely playable, though I can't give you a number of frames per second. It just feels smooth and I believe I did turn up the quality settings a bit when I first installed.
For what it's worth, with this card and the latest AltiVec-enhanced version of Quake 3, I occasionally hit 100 FPS with all the settings turned all the way up at 1024x768. Back when I had a Rage 128, I think I had to turn the quality settings down pretty low to make it smooth at 1024x768, and I definitely would have never have come anywhere near 100 FPS.