PC Pro magazine did a megatest on 58 CPUs back in October.
It is online here
http://www.pcpro.co.uk/labs/146/cpu-megatest/p roducts.html
Remember laptop CPUs are different from Desktop CPUs.
In your list above. the best Intel is the Core duo, then the Core Solo, and the Celeron is the slowest.
Most reviews I have seen say the Core Duo is the best CPU around at the monent so try to get a laptop with that (not sure you will get one for under �500).
Not sure how the AMD compares with Intel.
Remember Windows Vista comes out at the end of January, you may want to wait for a laptop with that on it.