I'm running a Celeron 1.4 GHz Tualatin with Asus P2B BX board (from 4 years ago - used a Celeron 366 back then). I can play Unreal Tournament 2003 pretty well with a Radeon 9100. 40-110 fps on indoor maps at 1024x768x32. WinXP flies (512 MB).
Used an Upgradeware Slot-T adapter. Costs US$20. CPU was $60. The BIOS recognizes it as a Pentium III 1402 MHz. Celeron Tualatins are 100 MHz FSB unlike the Tualatin PIIIs so the the AGP bus is not overclocked.
I had to update the BIOS on the Asus P2B though, and my rev. 1.10's VRM supports 1.5 V. It may not work on older mobos with an older VRM, and it may not work with older BIOS.
OTOH, I also tried that Celly on a new Supermicro BX mobo I bought 2 weeks ago. No BIOS flash needed and I think the BIOS were several years old. Mobo cost me US$30. It was a rev. 2.0 mobo though, so maybe that helped. The BIOS only recognizes it as a 1000 MHz unknown chip, but it runs fine, and at full speed. I hear this is what happens with lots of older machines with this upgrade, but they work. YMMV. The PowerLeap adapter is an option but it might not work either, and it costs a lot of money.
Coppermine at 1.8 V is also an option that could be tried if your mobo VRM won't handle anything lower. You'd want a slot adapter with voltage jumpers, with socket chip though, NOT a Slot 1 Coppermine. That way you can choose whatever voltage you want.
If you're not willing to take the chance for a Coppermine or Tualatin, then I'm not sure I would bother upgrading it. You'd be stuck to something like a PIII 550 MHz Katmai, not necessarily the best idea unless money is really tight and you can find a Katmai cheap. Just upgrade directly to a P4.