My setup: Shimano SPD M520s and MTB shoes (Specialized Riata, which probably doesn't help you much since it's a women's shoe).

I have never ridden straps because I learned to ride a road bike and clipless at the same time. I have, however, put thousands of miles on my setup on all kinds of terrain, and I would highly recommend it for beginners.