I had similar experience with AT&T. Plus the classic dropped calls for no apparent reason.
When the iPhone 5 came out we switched to Verizon. Number porting took about an hour... and it was iPhone 5 release day.
Verizon has been much more reliable for me. I get service inside the Lebanon Coop Foodstore and inside the River Valley Club - both were dead for me with AT&T. I live in the Etna/Enfield corner of Lebanon and get 4 - 5 bars of LTE at home most of the time.
Verizon has also been solid for me in Boston, New York, San Francisco, Chicago and Austin.
Call quality has been about the same.
I also get LTE vs. 3G in a lot of Lebanon and Hanover. Given how long it took AT&T to turn on 3G here I wouldn't hold my breath for LTE service from them.
One thing to beware if you switch from AT&T - the moment you're gone you'll lose access to your account. Turns out I wanted some of my old bills and I couldn't access them anymore after my numbers were moved to Verizon.
The only downside for Verizon so far is not being able to use data while you're on a voice call. This hasn't been much of a problem so far but it did surprise me the first time it happened.
We pre-ordered our iPhone 5's through Best Buy (I wasn't awake when Apple sold out of pre-orders...). They handled the pre-order very nicely, had the phones the day they were released; emailed us the day before to confirm we made the first shipment, and set up an appointment to come in and pick up the phones. I was very impressed with how they handled the whole thing and will be happy to do our next phone upgrade through them. They get a lot of (usually deserved) grief but they deserve a big thumbs up for a good experience with that.