Hmmmmm...provider service seems to be a lot like real estate. It's "location, location & location".
I am in the Ozarks...Missouri to be specific, and Verizon is virtually nonexistant here. AT&T and T-Mobile are both popular as far as BlackBerry providers, with AT&T getting the nod as most used. I have never had a single issue with AT&T and either call quality or EDGE performance at all...with not only my current BlackBerry devices, but also with my previous Treo smartphones as well. I have several friends who use T-Mobile, and are not nearly as satisfied...and all have BlackBerry 8800's.
My Curve is plenty fast browsing the web, and gets excellent phone call quality and reception. My advice would be to call AT&T technical services from a landline, and have then do a "re-register" of your service. That basically means that they wipe you totally off the service...then re-establish your service, repositioning you to new towers. It was the savior for me when I was using my Treo...and it just might be what the doctor ordered for you and your BlackBerry too.