I swear by Rockports. And by Off Broadway Shoes store (which sells big brand shoes but at a noticeable discount):http://www.offbroadwayshoes.com/
I bought Rockport casual/dress shoes there and some sneakers last year, and they're by far the most comfortable I've owned. I kept thinking something was wrong with my feet, but I think I just spent too much time walking around in $20 shoes/sneakers I bought from Wal-Mart and K-Mart that kept wearing out in record time. I found if I paid maybe $50-$70 for something good (about what you pay for new games these days) there was much less pain.
While it's possible to "break things in," I never felt really comfortable in shoes unless they felt fairly comfortable to begin with. My closet's full of past dress shoes that Never Quite Broke In.
While I haven't turned into Imelda Marcos
, the fact you can bring back in a receipt for shoes you bought there, to get a discount on your next pair, can be enticing.