I also like SPD cleats. There are plenty of SPD shoes that recess the cleats so you can walk in them. I look for shoes with very stiff soles. The stiff soles spread the force from the pedals across a large area of your foot to prevent "hot spots". The shoes get the clips recessed by placing a border of rubber (or similar) around the edge of the sole. I look for shoes where the rubber is soft and grippy, so the shoes won't be slick if I walk into a store. There are plenty of SPD pedals and shoes, because they are frequently used by mountain bikers. You should be able to get decent pedals and shoes for less than $200.
Make sure you ride in these a good amount before starting your tour. You want your feet to acclimate to the shoes gradually.
When learning to learn how to ride with clipless shoes, there are two kinds of people -- those who have fallen over, and liars.
The problem is, you have to remember to clip out before stopping. Most people do OK when they first start. After a while, they think they've got it. Then they lose their focus, forget to clip out, and fall over as they stop. My fall happened next to a car of attractive young women. It hurt my pride. This is just another reason to ride your new shoes a good amount before starting your tour.