I've Been Down This Road Before
Not precisely on point, but in the past year, I switched from iPhone 3GS to Blackberry (the Curve on Virgin) and then to android (the Intercept on Virgin). My reason for switching was AT&T's poor coverage and non-existent 3G in my area. After spending time with BB and Android, I am now strongly considering returning to iPhone with the Verizon iPhone 4. Why? Ease of use, apps, and availability (finally) on the carrier with the best coverage where I live (in comparison to AT&T, Sprint or T-Mobile).
Blackberry is especially limiting due to its OS (Virgin's Curve runs OS 5). Although you can email, text, BBM, check facebook and twitter, get RSS feeds, play music, read books on the kindle app and do some limited web surfing, the user experience overall is limited in comparison to both Android and iOS. In general, everything is slower, especially any attempt at browsing the web.
Android is a better OS than BB and offers a user interface similar to iPhone in terms of ease of use, features and apps, but for me it was not quite as good. Part of that was the hardware I was using (the Virgin Intercept) and part of that was the carrier (Virgin piggybacks on Sprint which is better than AT&T but weaker than Verizon in my area). I was able to sync my music, surf the web, and sync multiple email accounts and calendars with gmail and google calendar. The majority of the most popular iPhone apps are available on android. The user interface on my particular phone, while better than BB in most ways, was not nearly as good as iPhone/iOS. There are a lot more things to fiddle with on android if you like to do that.
I have tested various higher end android phones (Samsung Mesmerize, HTC Desire, Motorola Droid, HTC Droid Incredible) and while they are very good smartphones, they are not clearly superior to iPhone. HTC's Sense UI is very appealing and coupled with the design and build quality of the Desire, presents the closest thing to the iPhone that I personally tested (IMHO). If you are curious about android, I would recommend you pick two or three of the newest high-end models on the best carrier for where you live and then go put your hands on them to determine which one offers the best build quality and has the best user interface. I recommend trying a variant of the Samsung Galaxy S, an HTC model and a Motorola model. Then compare your favorite phone, the cost of the accompanying plan and coverage with your current iPhone 4.
Lastly, if you live in an area with great 4G coverage, that may be a factor you want to consider as well. All 4 major carriers have some version of 4G in many major markets in the U.S. and for now, if you want to get in on that, then your only choice is android.
Best of luck to you. Sorry for such a long post. It is a topic near and dear to my heart.