I like trailrunners in the dry desert sands but as you figure on getting wet in the surf, my choice might be good sandals you can walk far in with no problems. I like both Chaco and Keen sandals bur you have to be used to them before the hike of course. The thing there is, they do rub sand on certain points and will give you some skin damage after the miles add up. In a few weeks your feet do get tough in those spots but that won't help for the first few days. When we do our 30 mile+ hikes in southern Utah, in and out of shallow streams constantly, we put on some kind of liquid skin on the points we know will rub. Girlfriend keeps the stuff and I forget the brand name.

The one thing that really helps a lot over sand is trekking poles. They make life a lot easier and movement much more flowing.