The simple fact that you can pull up on the upstroke with your leg as well as push down on the downstroke gives you an advantage. You can utilise different muscles for power gain on an all out sprint, or to reduce fatigue over longer distances. For comparison, try pedaling with one foot only. On a flat, aside from being a little jerky trying to catch the upstroke through its momentum, you are completely unable to lay down any power at this point. Your foot just follows the pedal. With a cleated pedal / shoe, you can maintain power throughout the revolution, even top and bottom dead centre by pushing forward and backward.
Indeed, one footed is a great way to practice with cleats, as it builds technique, smooths your pedal stroke, and applies power more evenly leaving you more power available from you muscles. This is especially noticeable when sprinting and climbing steep hills out of the saddle.
Add into the equation the stiff soles of the shoes, and this gives you even more efficency as you're not using some of your power to bend your sole.
I'm not going to get into the argument of what a proper cyclist is, each to their own and all that, but I believe anyone doing decent distances on a half decent bike will benefit from cleats.