I backpacked in Europe for a month last summer and we walked EVERYWHERE. Other than taking the trains and the subway twice, we walked (which was nice since I lost 10 pounds while I was there)!
I did something very out of character for me...I only took two pairs of shoes. I took one pair of Merrel sporty sneakers and pair of brown leather sandals, I think they were Clarks and were actually somewhat cute. I made sure to take things I wouldnt' care if they got dirty/scuffed/ruined.
I think the places you are going will still be somewhat cold in May, so you may not seed sandals. What about Uggs, a pair of sneakers, and cute flats?