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.
P.S. welcome to anandtech forums