My skinny-heeled flip flops are a bear to walk in and are more for fun (dare I say fashion since I bought them at a highly inflated price at Bebe?) than function. I have to go to Old Navy to shop for one of the S.P. locals, so I'll check out the platforms, Kimmay. My criteria for shoes continues to be whether they can be rinsed under running water and still stay in one piece. I say this after ruining several pairs of sandals on prior trips. I love to walk around the island so I also bring good walking shoes along.
Also, if you plan to do any boating or diving, it's important to have a pair of skid-proof shoes/sandals so you don't kill yourself walking on the dock or getting into the boat. Another piece of advice from my "been-there-done-that" list.