Sandals in the winter? Other winter footwear options?
I go through 3 different types of shoes as the seasons change:


Hot (80F+): sandals 
Variable (30-80F): indoor soccer shoes (eg adidas sambas) 
Cold (30F-): light hiking boots/trail running shoes


For cold weather, you not only need to be comfortable while pedaling on your bike, but also confident off your bike. Lightweight hiking boots, with windproofing, waterproofing, and breathable layers, not only keep your feet happy while pealing but also let you feel like a mountain goat when you put your foot down in the slush at a stop light, or dismount on top of ice, or have to portage down wet stairs. Trail running shoes with these attributes are also a great choice if you want something even lighter and without the additional ankle support.

As others mention, wool/smartwool socks and switching to platform/toe clip/half-clips on your pedals are both good changes in addition to changing up your footwear. My winter setup is smartwool socks, size 13 light hiking boots from North Face and Velo Orange half-clips.