You want to look in casual and touring shoes, or ATB lite. You want a sole with a
recessed cleat and a soft walking surface. Pure ATB shoes have aggressive soft
treads with a deep waffle/herring bone tread. You want a tread about 3-5mm deep.
Road shoes are bad because they have a hard plastic sole with tends to slip right off
the pedal if you mis-position the shoe and it doesn't lock in immediately. Soft sole
shoes are less likely to do this. Recessed cleats are standard with casual, touring and ATB shoes. Both Frog and Eggbeaters have small cleats that fit into recessed
shoes with ease or only a bit of trimming of the pocket in the shoe. Some to consider are the Shimano sandles, Lake 100 or 110. Look for shoes that have a
rigid sole, if you can flex them in your hands, you can really flex them on the bike and
they are not likely to be comfortable. Bike shoes of European origin tend to have
narrow sizing, and many shoes are like womens clothing the rated size is much smaller than the actual size. Shoe tables show I should wear Euro 43-44 size but in cycle
shoes 45.5 or 46 is a better fit. Woe to the rider with under sized shoes. I also like
the get shoes large enough for an insert, as cycle shoes have NO inside sole pad and
large enough for an extra pair of socks in winter. Velcro straps make tightening the shoe easy. Finally buy shoes locally, they are cheaper mail order but one sizing mistake and return shipping will eat up the difference fast. Think oversize, think LBS. Also Speedplay website has a discussion of shoe compatibility with their pedals. The problem is mostly with large feet say US 12 or larger, they make pedals with longer axles for clearance purposes.
Steve