I agree with Dave B. Back in 1988 I bought a pair of Look pedals. It was wonderful cycling and not having my toes go numb from the toestraps. Unfortunately this was before Look invented the floating red cleat so one of my knees hurt from being fixed in place. So back to toestraps until the summer of 1992. Used Time Equipe pedals, and Duegi road racing shoes, to tour Europe. Pain changing shoes whenever I stopped but the floating Time cleats were wonderful. This was before floating mountain bike cleats were invented. Bought a pair of SPD pedals and cheap mountain bike shoes in 1997 and toured some more. Easy walking and comfortable shoes. Except the shoe soles were flexible and my feet hurt after 50 miles with the SPD pedals. Bought some Carnac stiff soled shoes years later and feet did not hurt from the SPD cleat until about 100 miles. Small SPD cleat hurts no matter how stiff your shoes are. But stiffer shoes postpone this problem. Stiffere shoes are not nearly as easy to walk in though. Couple years ago I bought a pair of SPD sandals, Lake. No hurting feet at all from the SPD cleat. Even though the sandal soles are not too stiff. Kind of odd. Maybe the comfort of the loose sandals overcomes the small SPD cleat somehow. I also use Shimano M737 SPD pedals. These have a platform of sorts around the spring mechanism. More support than the M747 or M520 models I also have. Larger platform probably helps too.
Next time I go touring, I will use the Lake SPD sandals and M737 SPD pedals as my only shoes. On and off the bike. The cleat is recessed enough it does not make too much sound when walking. Lake sandals are comfortable for walking.