Soft-soled shoes are not good for bike riding. Or horseback riding. http://bicycleapparel.com/shoes.html

There are several cycling shoes for platform pedals available with stiff soles. Google "Touring shoes"



As buelito said, you'll still need good inserts inside the shoe.

I had numb toe problems with my clipless cycling shoes until I found the Superfeet inserts. I use the black ones. http://www.superfeet.com/activity/cycling.aspx

My suggestion for trying on cycling shoes is to do so after you've been walking a lot and your feet have swelled. You don't want the shoes to be too loose or too tight. The insoles that come with the shoes may work fine for you but I have low arches and needed different ones.