First, I think the celerons above 1Ghz used tualatin core, which isn't compatible with even a ton of PIII boards. Second, if he has a good BX chipset, its possible to run at a 133Mhz FSB easily (if you're inclined to OC). So he could use a fairly fast PIII. If not, even at 100Mhz, there were some (coppermine?) celerons that went fairly high. You could pick up an 800Mhz celeron for $40 and then just get a slotkey adapter as suggested above. If you wanted a really simple solution you could just pop in a 500Mhz slot 1 PIII, for around 40 or so.
I would not spend money on a Celeron or PIII solution, if it required you to get a new board. I think at that point it'd be cheaper and better to buy a cheap Socket A board and a 1Ghz+ Duron or something. Very affordable, you could get a KT133A that could use your existing memory. Or get a KT333/400 and some DDR if you want to spend a few more bucks.