Consider the Palm Pre. I've been using one for about 5 months and really loving it. If you're opposed to Sprint, it'll be on Verizon soon.
Otherwise, I've heard good things about the Android OS. It apparently doesn't handle switching tasks as well as the Pre (but, you can multitask, unlike on iPhone). And WebOS (Pre) actually integrates better with the Google calendar and contacts than Android does, at least according to what I've read.
I'd rank the major smartphone OSes this way:
1) Web OS. Best overall OS. It's got a very comfortable interface and really embraces the idea of cloud storage. There's an active "homebrew" app community that supplies more apps than the official catalog, which is growing. The hardware isn't bad, but that's probably where it's weakest -- high on style, low on power, but WebOS is pretty snappy, anyway. It's just that comparable hardware would blow the competition away. It also has the smallest form factor of all of these, which is both a positive and a negative.
2) Android. Google will support this sucker, so you know it's long-term. Even though it's sync isn't as good as Palm's Synergy, I can't imagine that Google will remain content with that. I believe they have a good sized official app catalog, but I don't know about homebrew. Droid is, by all accounts, a darn solid phone.
3) iPhone. You know the drill. It's Apple, ergo shiney and stylish. Biggest app catalog around. Homebrew is stomped out with jackboots, though. But, vast amounts of hardware cradles, speakers, etc.
4) Blackberry. Great for business, but mediocre for personal. I have no idea about apps. My entire experience is based on using a locked-down version at work and having friends who have swapped out their personal BB for one of the above. A plus is that I think certain models will also sync multiple Google calendars.
5) Windows Mobile. I used to use this. Not overly impressed, even as a .NET programmer. My understanding is that the latest version is much better, and I was running one of the older phones (not 3G). On the plus side, it syncs with Outlook very well. MS has also added an app catalog.
Of course, YMMV. Needs are different. What I was looking for was something to sync up my various stores of contacts, seven Google calendars (work, personal, wife, and four kids at a glance), multiple email accounts, multi-tasking, and music. For most of those, the Pre won. I considered the HTC Hero (Android OS, no physical keyboard), but it didn't seem to have anything that it did better than the Pre and the Pre was about half the price.