Virgin
If you have the cash, go for the Compaq Ipaq 3600 series. They have a 32MB and a 64M version. The latter should keep you going for a year or so. 32MB surfices for me, however you are limited to storage space. I can store two or three good movie clips at time.
Wireless internet is around the corner. Ipaq with its colout TFT screen would be best for this I believe.