I would go for a Nokia E61, avoid HP iPAQ's as although they appear to do everything, the battery lasts for about 2-3hrs, and is very fiddly to use. I have both, and default to the Nokia every time, will do most things, and the battery will last a couple of days.
AAF