As Mel says, the best thing to do is go and try on a lot. I am on my second pair of Northface sandals, I think they are called hedgehogs, which I find very comfortable. I also have some which I think are Ecco (they are so old I can't find a name on them) which are great over short distances but not so well cushioned. I tried on an awful lot of sandals before settling on those though. Some people prefer sandals with covered in toes, which is protective and might get fewer stones in them, but I don't get on with them so well.
I have tried on a lot of sandals which I find positively uncomfortable. I was told Keen were really comfortable, but they gave me blisters. Walk round the shop in them for a while before you buy, and if you have any doubts, look further.