The Tualatin Celeron 1.2GHz is actually quite fast. Even with the memory bandwidth limitations of socket 370, I have seen many benchmarks where it has matched gaming framerates with an Athlon XP at the same speed. In answer to your question, 1.2GHz is just about the minimum cpu speed needed to feed a modern video card enough horsepower. With the exception of the Radeon 9700 and Geforce4 Ti4600, I saw a whole bunch of video cards tested showing a relatively small increase in fps above 1200MHz. Of course, this is real world gaming perfomance, benchmarks show a huge increase with faster cpu's. I would try the 112MHz fsb setting on your motherboard, if one is available. This will give you 1344MHz, and if you don't have core voltage adjustment, then use the wire trick to get 1.675 volts. If your whole computer experience isn't about benchmarks, then any of those video cards you mention will play games wonderfully with the Celeron 1.2GHz.
I assume by the cards in question you are probably running a GF2 or similar, and the added features in the newer cores are deffinitly worth the upgrade to a GF 3 or 4. I am running a celeron 1100 and recently upgraded to a gf4 ti4200 64 meg from a gf2 ti. I noticed substantial increases in game performance, as in SOF II before the upgrade would bog down occasionally and generally run at a "lower than my liking" average fps at 1024x768/moderate ansiotropic filtering setting/no fsaa. Now it runs great with full ansio and 4x fsaa. Battlefield 1942 also runs tons better, but my experimentation with settings has been less extensive. In my opinion it was deffinitly worth it.