Yeah the original Celeron was absolutely horrible without any L2 cache and the slower bus. Once the Celeron 300A hit the scene, it became pretty respectable.
I think mostly because that thing was so easily overclockable. I remember running my dual 366A on an Abit BP6 to 550, perfectly stable on Windows XP with stock cooling.
Well, you could also put them on slot-1 cards and solder them up to do dual processor. Saving yourself a few hundred bucks in the processes. For the money they weren't that bad a deal.