Allen Edmonds do a very nice pair of shoes with rubber soles and arch support. That brand received wide acclamation here when I asked a while back. I bought a pair and it was a real hassle, and shipping was extortionate. But the shoes are seriously nice.
My husband wears only Nunn Bush. He prefers the Marcell (83364). They have the gel insole and are very comfortable, so he says.
Ecco size 45 seem like they are custom moulded for me.
I’ve had good luck with Clarkes and surprisingly, Skechers.