I have worn New Balance, Nike, Rockport, Clark, and they ALL wear out on the bottom too quickly.
This is the problem I have with shoes, the heels go out first. A long time ago, they made soles a lot harder. Then they came out with rubber type heels with air pockets in them for cushioning. I am lucky to get 4-5 months out of shoes. When I started driving, I wore Sears Diehards. Then I went to HiTechs in a boot. I tried some Nikes once, they wore out in one month. I then started trying hiking boots and shoes. The Rockports and Timberlands used to be good, but the soles and heels got worse as far as quality. I just bought a pair of Nike Air Monarch 3s today, I got them cheap and will try them. I really hate to go with tennis shoes, they don't offer good ankle support. But I will see how these do, I will alternate them with another pair of shoes.