Verizon definitely has the most coverage, especially in rural or mountain areas where other companies have not yet begun to offer coverage. However, you have to pay more for the same amount of minutes, their phones aren't as good, etc. They really seem to favor the Motorolas, which are universally pieces of complete dog sh!t. So it depends what you need most.
I have a T-Mobile phone, and am happy with what I get for the price (very cheap for the minutes), but they definitely do NOT have the best coverage. My experience is that they only have coverage where AT&T already has coverage, and they are missing some of those areas. So they are worse than AT&T, which is already a lot worse than Verizon.