I have lived in 4 different rural markets and regularly travel between them. Currently, in NC, Verizon is everywhere since they bought out a couple providers like Rural Cellular and I forget the other one.
When I left Verizon, they had full bar 3G coverage at my house. They had just upgraded about 3 months before I went with an iPhone. With AT&T, I need to drive almost 20 miles to even find 3G coverage.
With Verizon, I had a Palm Treo 700 and it was very rare to see even the analog signal at all.
If Apple would make the iPhone for Verizon, i'd switch back in a blink, even if I had to pay early termination, it's that bad. I typically lose between 20-40% of my calls. There is several dead zones too, that I can't even drive down without losing it.