Know everything about cold weather mate! and know I can handle it a bit better than south ppl since Im Norwegian. (yes im stereotyping myself)
Did a tour around Ireland in february/march and got to experience heavy rain cold weather and wind. I would reckon thick socks, the sandals and the Gore tex footcover im gonna take with me should be enough, if not an extra pair of socks under the thick ones.
The BOB is only if I cant fit my guitar on my bike, ( and for the notice, I play double bass as a main so i actually did take a HUGE step down from what I wanted to bring with me) besides, how much does spokes for a bob weight anyway
I have actually never tried cleats before! but what from what ive heard of tourers ive met on the road, they use more muscles/different muscles (more right muscles?) when theyr pedalling so it becomes more comfortable. I recon I wont get so much more fsat other than the possibility that i could get further because of better muscle use.

ehm the reason I got 3 shoes is because I get very warm, very sweaty in sneakers, sandals is nice for showering in dirty hostels and in warm weather, and normal shoes (lightish) for actually being social and going out drinking
Some other tourers have reviewed using the sandals when touring and they LOVE it, they may not be suited for below 0 degrees rain and wind weather, but if that is the case im would have to buy some winter shoes until spring comes and ship them back home after

Besides, sandals dries a whole lot quicker if you actually get wet,
I did try waterproof socks in ireland, quite expensive, and they were waterproof, but the only thing seperating the water and my skin was some kind of thin plastic so the cold just dragged all heat out of my feet! was running sneakers only then, quite cold even if I didnt get wet ( just got the feeling of being wet)