+1 to the Psion Organiser ... all you need to be happy is a Z80 and a copy of Zaks. (Wow, I'm getting old ...)
Seriously, I own an HTC Desire and I'm very happy with it. To my mind, one of the major advantages is that HTC doesn't have a paranoid desire to control what you do with your phone.
If you want to install apps from something other than the official Android Market, you just have to check a box. And at least on my Telstra-supplied Desire, that box was checked by default
This (humorous) video pretty much sums it up:
YouTube - iPhone4 vs HTC Evo