I can recommend an Android phone as I've used this one for a year. There is
one huge difference though - while the iPhone requires iTunes to put music,
photos etc. on it the Android mounts as an external drive and you copy files
directly. DoubleTwist can automate the process but I don't use it.

Verizon is suppose to be coming out with a new phone, I believe in July,
that is to compete with the new iphone. Check with you local Verizon folks
to make sure. I understand it will be Android based.

I have just bought a Blackberry based on the great tarif I had access to here in
the UK, but although Blackberry dont support linux, there are of course people
out there who make programming for it and one such is called Barry, I just had a
string of emails back and fourth with the maintainer. This software here does a
lot.