I love my Birkenstocks.
I'm a nurse, and have 2 pairs for work, along with 3 pairs of sandals.
It does take a while to get used to them. My sandals seemed to take less time than my clogs. There are several different types of Birkenstocks though. My sandals are Birkies. I actually wore them at MK, 2 days after getting them, and had no problem, but I wouldn't reccomend that, if you've never worn them. Try wearing them around the house a few hours a day, at first.
My DH swears by his Tevas. It took me several years, and finding a pair on clearance to convince him, but now he loves them.