I thought I was tired of at&t too and went to Verizon. Terrible decision that cost me my unlimited data plan. And the network? Overrated and worse then at&t. Hated it and went back to att.
Interesting, it's more of a coverage thing for me, there are places in Nebraska where AT&T has nothing and Verizon will be full bars.