The city of Konstanz, where my partner once worked, was our home base for the bicycling trip around Lake Kontanz. It really grew on me this time around: it's far out of the usual tourist rotation for Americans but very popular with Germans. It's more vegan-friendly than anywhere in Switzerland or Austria. Transportation is pretty good, and there are things to do.