I cycled 13 miles in 50 mins this morning in cotton socks and these basic fashion leather boots. No fancy lining or anything, just plain old tan boots. Admittedly, my toes were getting a little chilly toward the back end of the 5C ride, had I been sensible and pulled another pair of thick woolen socks over the top I would have been toasty, alas I'm perpetually running late. Avoid shoes with ventilation, and if your extremities suffer, it might be worth getting windproof/fleece lined boots or something. Leather boots are naturally windproof and seams can be waterproofed with wax/fat. I use equestrian dubbin, nice and cheap and a pot seemingly lasts a lifetime. Riding with these means I can hop right off the bike and not worry about changing in the office or about town for social stuff. Just like any normal day.
I have suffered with foot pain and cramps in the past, but as mrj says, if you have the right size pedals, particularly with a large platform, it stiffness of the sole doesn't matter much. My last pair of pedals were awkward with any casual shoes, they were double sided SPD pedals, with one side for normal footwear, but because the centre of the platform was hollowed out, my flexible casual shoes caused pains after 5+ miles of reasonable pedal effort. No such pains on my new more supportive flats.
