1) If you cancel you preorder, it can take AT&T up to 3 days to reverse your upgrade eligibiity. So even if you find an iphone in an Apple Store, you will likely not be able to buy it using your upgrade if you cancel it when at the apple store. Sometimes you can get lucky tho...
2) For AT&T customers, you must find the phone at an AT&T Company store, not an AT&T Retail store (or Apple Store). Retail stores cannot reverse/reset your upgrade eligibility once you cancel your order (apple.com). Company stores can.
3) To find an AT&T company store, go to AT&T Maps and look for stores that are Company Stores, not Authorized Retailers.
https://www.att.com/maps/store-locator.html#fbid=FhP_sQV-wY7
4) I bought my iPhone 5 on release day from a Company Store with no crazy lines. Seems people think they'll only find one in an Apple Store. Hoping I can try the same.