I'm going to add an unconventional option. I travel super light with only one small duffel bag. In wet, cold regions, my second pair of shoes are Super-Birki polyurethane clogs from Birkenstock. (My first pair are leather boots.)
They have supportive insoles, lots of space for toes to wiggle around, and thick soles with good traction. They keep my feet as dry as rubber boots in rainstorms, provided I don't wade into deep puddles. They're also great for walking on beaches at low tide (when there are pools of water) and in muddy or boggy areas. Best of all, you can clean them in the shower and dry them with a towel and put them right back in your bag to travel. No waiting for them to dry! They're lightweight in my bag and spacious so you can stuff them with all sorts of small things. In cold weather, I add a pair of wool socks. Their thick soles keep my feet warmer than my leather boots. In warm weather, I wear them with light, low socks or go sock-less. I wear them with both pants and dresses.
They're obviously not great for bicycling or walking on hilly cobblestones. That said, they still served me well walking around Siena (Italy) in winter. They were perfect for Scotland and Ireland, plus anywhere rural.