I got an Android-based HTC Magic phone from Vodafone Australia. It's very good, and a great achievement that this is all possible with free software.
It's a very nice platform for Linux-based users: it appears as a USB storage device, so you can copy photos, music and videos to and from the phone without needing any special software - in fact, it doesn't even come with any proprietary Windows software, as most other phones do. Assuming you're happy to already use GMail and other apps, it will transparently sync across the network, and this should be reasonably cheap if you have a wifi network.
The UI is all you'd want: fast and responsive (notably more so than some recent Nokia phones), attractive and innovative in for example the way notifications are displayed. There's a distinct feeling of what apps should be and act like.
The on-screen keyboard is quite usable, because it has quite smart suggestion and correction. I think it's roughly as easy as a hardware phone keyboard. (Though I've owned a Blackberry, and they may be better.)
I have seen some application crashes, but only rarely. The whole phone has not yet crashed on me, and I've seen no sign that it degrades with use.
The voice quality is very good. I have hit some situations where the quietest phone volume is too loud to hold to my ear, or the loudest available music volume is quieter than the phone volume. (Possibly because the track was recorded at low volume, but it would still be nice if it could scale it up.)
The camera is not great, but what do you expect from something smaller than a pea. The
photos are reasonably crisp. (That one was tweaked a bit in gimp.)
There are a few useful UI shortcuts, not mentioned in the manual: pressing and holding Home brings up a quick-switcher of the most recent six applications, and pressing and holding Menu brings up the on-screen keyboard, even if there's no text field visible. You can use this in the Contacts app to do an incremental search through the contact lists.
