I can also recommend ECCOs. I bought a pair of brown leather walking sandals a few weeks before a 6 week European vacation. The only time they were inappropriate was walking through snow in Switzerland so I switched to waterproofed boots :) They have a good-thickness non-slip comfortable sole and two velcrose straps to make sure they fit correctly and comfortably. They were comfortable walking over rough cobblestone streets and hiking up steep roads or through paddocks :) The inner didn't smell the whole time I was away (or for weeks upon my return) and they can be easily but carefully cleaned. I bought them in Aus but I saw them at the same conversion price in a shoe store in Rothenburg.

I too would not feel comfortable buying shoes over the internet as I tried on maybe 8 different pairs of walking boots in a store and none were comfortable even with varying sock thicknesses even though they were all my size. :) Megan Brisbane, Australia