I would read through this thread:
https://bitcointalk.org/index.php?topic=84669.0 first. I would not even consider an iPhone or for that matter any other phone in a "walled garden" such as a Windows phone for Bitcoin.
That leaves Android phones, but check first that the ability to install applications outside the Android market has not been disabled by some dinosaur carrier. Also phones running GNU / Linux with third party GPLv3 / AGPLv3 code where such code needs root access in order to be modified are a good choice because they cannot be locked down for licensing reasons.
Your best option is an "unbranded" unlocked no contract phone.
This is honest pretty much impossible to beat:
https://play.google.com/store/devices/details?id=galaxy_nexus_hspaCarrier locks suck for a lot of reasons. It makes the phone worthless if you wan't/need to leave the carrier. They know this and that is why they do it. Also carriers are horrible for upgrading phones to latest version. Lots of people got trapped on Android phones which were Android 2.x capable but the carriers simply never upgraded them (and you can't unless you root them).
