phew This is a question with highly subjective answers.
During travel, and while actually moving from one place to the other I always wear my hiking boots. Usually I have light boots, like the Lowa's "B" class of boots: They have soles that prevent you from slipping, protect ankles, have some hard (rubber-like) protection on the side of the shoe and are padded in all the relevant places. I don't want to advertise any particular brand. You can get these type of light hiking boots from lots of places, and lots of brands. I always wear them when actually moving around with my backpack because they are the heaviest.
I then sometimes - always on the long trips - some very light sandals for the beach and warm areas just as Jonik mentioned already.
Both are bad for any "elegant" ventures. But I never had trouble getting into a restaurant or even casinos. (Well, the more traditional casinos in Germany, where I live, would not let you in with shoes like that).
To be honest, I believe most backpackers don't venture into such "high-class" establishments and therefore don't need "elegant" shoes.
Consider good socks as well: Thick hiking ones for the boots, and thin for elegant shoes.
But most importantly the shoes (and socks) have to be light (for carrying around the world) and comfortable! Take only what you absolutely need.