Add my vote for New Balance cross-trainers or walking shoes. I have heel spurs & a bad back, so I am very careful about shoes. I never wear any shoes without also tossing in insoles (the gel ones may be helpful to you, although I'm not crazy about them) & arch supports. I've noticed that when I don't have these additions tucked into my shoes, the ground seems a lot harder!