If your going cheap, get the PIII 700 and overclock it to 933. With a 97% success rate at most overclockers sites, it's as close to a sure thing as you'll get.
if you really like the 800, there are two versions, the 800E and 800EB. The 800EB has a 133MHz FSB and performs much better. But even the 800E beets the Celeron 1GHz.
What's the frequency, Kenneth?