a few questions need to be answered first:

Do you need Vista/XP? (would not recommend vista on low powered machines). If so then go with either a UMPC or one of the minute Sony's (they also have a built in keyboard)

If Linux is ok, then Asus EEE pc looks great and is very cheap.

If you need mobile broadband then go for the Toshiba G900 as it has a good keyboard for occasional use plus it also has a 800*480 screen for surfing. it is also not much bigger than a phone.

800*480 would be minimum screen size for surfing.

W.