Another vote for neoprene booties. Whatever brand you get, you'll likely want to reinforce the sole at least. Otherwise, you'll get limited life out of them.
Use ShoeGoo. There's a page in the VeloWebGarage on how to make them bombproof. I've gotten 5 seasons out of one pair by following the pre-emptive reinforcements detailed there.
On edit: On really cold wet days here, I'll add a pair of coated-nylon covers over the neoprene, for added waterproofing and warmth. Otherwise, one's feet will soon succumb to the cold. Painful lesson.