I ride with clips and straps, too.

For multi-day tours where I'll be off the bike a good bit and only want to bring one set of shoes, I wear North Face Hedgehog Gore-tex shoes. Sole is stiff enough that I have no problems even with 60+ mile days (occasionally :-); sole is good for hiking, but not so aggressive that it hangs up on the pedal cages; Gore-tex keeps me dry; and they don't look dorky.

For day rides, I have a pair of Shimano SPD mountain bike shoes that I use. Just don't mount the cleats to the sole. Pretty good for average walking around, too.