A Celeron is a crippled Pentium. Anandtech ran some benchmarks a while ago which showed that the AMDs blew Celerons out of the water every time, so there is zero point in going with a Celeron IMHO.
There really isn’t any user-experience difference between any of the processors out there. If you want to approach the issue in an optimizing way, you could decide how much you want to spend, then think about what sort of stuff you do with the computer, and then check out some benchmarks to figure out which chip will perform fastest for those tasks within your price range.
For memory bus speed, you’ll want it to be synchronous with the processor’s FSB, so once you’ve picked your CPU your decision has been made. At least in AMD-land, the 333MHz processors are about the same price as the 266MHz’s, so you may as well go with the faster memory. Memory prices are almost the same no matter what the speed is. One issue – if you choose a motherboard based on an nVidia chipset (certainly the NForce2, not sure about the '3) you will need to verify that the memory you buy is compatible. The NF2 doesn’t function with a lot of the memory that is out there. Don’t let this put you off the NF2, though – you can find memory that will work with it, and it won’t cost you any more; it’s just one more item on the checklist to make sure of.
Motherboard-wise, Asus is usually a good bet. You could also go for one of the new SFF PC’s like the Shuttle XPC or the Asus Terminator. I have an XPC sitting in front of me right now, and it’s a nice little box – the only negative I’ve found so far is that it simply will not accept more than one HD in it. Putting a second drive on either bus causes problems. Of course, you can always hook up a second HD externally via USB2 or FireWire.
BTW, another issue is how much you want to reuse from your old machine. You might well be able to buy just a replacement motherboard or a replacement power supply and be done with it. What blew? Did the cats really pee on it??
Personally, I focused more on small size and light weight, and it came down to either an XPC or the Asus Terminator – and since the Asus was an 18-month old design, and since the XPC was on sale. . . .