As an AT&T employee, I'm going to let you in on a little secret. Reception is currently changing for everyone, as AT&T users can no longer roam on T-Mobile's network. Not a big deal in some places, but in places like where I'm from, it's huge.
I have three active cell phones: a Blackberry Bold, iPhone 3G and the Google G1. The G1 is far and away my favorite of the three, but it's not for everyone. It has a capacitive touch screen like the iPhone, but it's not as responsive. It has a five line full qwerty keyboard that is unparalleled by anything out there. Out of the box, it's not terribly functional (in comparison to the iPhone), but unlike the iPhone, the G1 is completely malleable in it's operation. The G1 is a perfect balance between fun applications and "Web 2.0" business use.
The iPhone is the easiest, and the most fun phone ever. The capacitive touch screen is amazing, the new 3GS is speedy and nearly crash free (don't be fooled into the $99 3G!!), and there are millions of apps to use. My only qualm with the iPhone is that I use my phone for work a lot more than I do for play, and the iPhone does not excel in that area. If you're looking for a really fun device with lots of time wasting potential, nevermind a rockin' web browser, get the iPhone 3GS. Just remember, you can get 95% of it's functionality out of an iPod Touch.
What can I say about Blackberrys? They excel at what they do best, but fall lacking in many other areas. A Blackberry is first and foremost an Business Exchange phone. Email, Calendar, and Contacts management is arguably untouchable by any other mobile platform. I use my Blackberry for work. I send out mass text messages to staff, handle customer emails, organise my contacts within and outside the company, and write reports all on this device. The newer Blackberrys (Bold, Curve 8900, Tour) are especially good with excel documents, as the resolution allows you to see more rows and columns. Here are the major setbacks. Battery life of 3G/EvDO Blackberrys is quite lacking, and I rarely make it through the work day without charging my Bold (which has the worst battery by far, to be fair). There is a very limited number of applications that even come close to touching what has been done on the iPhone. The web browser in the new OS is very bad at handling scripting, so it runs just a bit faster than my old 2G iPhone. It's a business phone. They've done a lot to reach out to a broader audience, but at the end of the day, that's what it's for.
I'm partial to AT&T, so I'm not going to go into a tirade about how I feel about Big Red's business practices. Just know that in this brothers biased opinion, Verizon Wireless is one of the most backhanded, irresponsible companies I've ever known.
I wanted to go a bit into the nickel-and-diming. VZ is not alone in these practices, as there are plenty of peple with AT&T with the same problems. For both providers, the problem is more often than not bad provisioning on the account. For instance: if a customer does not want data on their phone (and it's not a smartphone) I will ask them if they would like me to block access to the data network to avoid overage charges. There is a drawback: even if you have unlimited messaging, MMS will not work if data is blocked. It's a matter of who your rep is, and how much they are willing to dig into your usage details. Whichever provider you go with, if the rep seems to be rushing you through the setup and explanation of your account, ask nicely if there is anyone in the store who specialises in account level provisioning (called SSRs at AT&T, not sure at VZ). If they are still dismissive, ask for a manager.
That being said, if you are getting an iPhone, the worry about nickel-and-diming is dropped to nearly nothing. I always recommend the 450 minute plan (unless you need more) with unlimited data and unlimited messaging. This comes to 89.99 a month - 98.xx after tax. Everything you buy is through your iTunes account. The only thing you can go over on is your minutes, which most do not.
I've rambled on

. If you have any questions, PM me anytime.