I have no complaints with Verizon, but also have friends who are very happy with T-Mobile. After hearing about their service rates, I can understand why. If you do
a quick Google search, you'll find several Upstate store locations.
T-Mobile's website reveals similar results. If you perform a search under "coverage", you'll see that the Greenville area is mostly in the "best" coverage category for voice service.