I have heard anecdotal references that suggest that Verizon does have fairly good geographic coverage here in the Midwest. I was a customer of theirs for a few years prior to the iPhone. Personally I didn't care for the way they seemed to nickel ad dime you for every possible different service, but times have changed. I'm sure you have looked at their coverage maps. You might also look at »opensignal.com
it's a user supported heat-map of wireless coverage, you may find it useful.