I have both Alltel (work) and Verizon (personal) and the Alltel coverage is far superior. I spent an hour on the phone with Verizon yesterday asking when the two will share the same towers. They would not answer my question and simply said that the total conversion process from the buyout will take until the end of the year. Alltel has also been very functional through the last few hurricanes.
I have heard that AT&T has good coverage as well.