A mountain type or commuter/touring type shoe will work with regular pedals, but so will a pair of sneakers. Sole stiffness will really make no difference on flat pedals while learning to ride, so cycling shoes won't really give you any advantage on flat pedals.

My take is to ride in whatever shoes you have for now. Then get clipless shoes when you are ready to switch pedals. That way you don't run into compatibility issues down the road between the shoes you have and the pedals you want to use.

They do make cycling shoes designed specifically for flat pedals, but these are really only an advantage in keeping your feet on the pedals when mountain biking or dirt jumping since they are grippy (and only then when used with studded pedals that probably didn't come with your bike).

Word of caution though; if you go with tennis shoes, do make sure you tuck your shoelaces in.