I'm currently travelling long term. Your priorities may differ from mine, I'm a male and care about the look of my footwear to the extent that they don't stand out or look obviously inappropriate for whatever I'm doing. I'll tell you what's worked really well for me.
All-black running shoes. As in, specialist running shoes. personally I went for Brooks Adrenaline GTS. They're not the cheapest shoes, but when you get gait analysis at a shop and buy a really well fitting pair, you get the following features:
- Very comfortable for walking long distances, in and out of urban areas. And of course, running. These things are built to support your feet and ankles for long-distance running, and will likewise give you a very comfortable walking experience over long distances.
- Highly versatile temperature range. They cover your whole foot tightly, but are made with breathable material that ventilate the feet nicely - so wearing thinner or thicker socks makes them equally comfortable for a cold winter or hot tropical climate, and everything between. A further advantage of the thin material is that they dry quickly if you get them wet.
- Light, and not bulky. Again, owing to the thin material. If you do find yourself packing them at any point, you'll appreciate this.
- Extremely durable. With a good quality pair, you likely won't need to replace them for years, especially if you're mainly walking in them. They will easily last you for your entire trip of 12-15 months. I've been wearing mine every day, hiking and playing sport in them, for months, and they actually still look and feel pretty new.
- They look right for most situations you'll encounter as a backpacker. Assuming they're all-black as mine are with no flair, they really don't stand out. You can wear them with pretty much anything. They look fine hiking, walking around town, in cafes, bars, restaurants. A really nice advantage you may not have thought about is that it's handy to be able to transition between these activities, without having to go home and change shoes (as you might have to with a separate 'scruffy/specialist hiking day shoes' and 'smarter night shoes' strategy).
- Can be used for a wide variety of sporting activities. If you want to occasionally have a kick-around, go to the gym, a quick run, whatever during your travels (I've done all these), you have a pair of versatile sport shoes. Dedicated hiking boots, for example, might be great for walking or gym, but might be a bit cumbersome for ball games. Versatility is the key. Running shoes aren't the perfect shoes for playing football, for example, but they're good enough to do the job if you just want to play occasionally.
I'd like to add I also have a pair of cheap, throwaway canvas shoes for use at the beach, or at the pool or whatever, or when I'm actually prepared for a night out and canvas shoes will look slightly better than my running shoes. However, I have no attachment to these, I could throw them away, lose them, and re-buy another pair at any time without caring, and they pack really small. So they're there, but I don't consider them a pair of shoes I actually need, I could do without them fine.
Having one pair of 'proper shoes' rather than two is fantastic. I've made the mistake of packing day and night shoes on past trips, and this way, for me, is much better.