Here's what I consider to be the best advice you'll get:
Go to different mobile phone stores and look at and play around with different makes and models. Try to do everything you plan on using it for. Get the sales person to show you the tutorials that most PDA phones come with to get a feel for how the device wants you to use it.
I could just tell you that I loved the Windows Mobile OS and hated the BlackBerry OS, that the iPhone OS is pretty good or that I didn't much like the Palm OS. But what I and anybody else do or don't like won't matter much if you get a particular device and find you just can't stand it. I got a BlackBerry Curve and I really wanted to like it. I tried so hard to like it that after the first time I returned it, I actually bought it again, and I still wound up returning it.
Same deal goes for the networks. Here you'll need to really on people you know who live and work in the same areas where you'll be using the phone to tell you how well the network works in that area.
Over the years, I have used Sprint or AT&T each a few different times. My wife has used Verizon for a long time. Each has specific locations where it doesn't work well, but some other network gets a pretty good signal in the same spot.
For the record, I now have the new iPhone 3G. For the first few weeks after I got it, I could barely get a low-speed signal where I live; suddenly, one day (and ever since) I've been getting a decent high-speed signal reliably. I do not seem to get as good a signal inside in general as my regular partner at work, which is most noticeable the deeper we go into a hospital. I think he has T-Mobile.