I've used trailrunners with mini-gaiters on them - they work pretty good for keeping it out if it's the elastic type
mini-gaiter with a nice close fit. Alternatively boots and gaiters.

The other problem is there is sand and then there is sand. some beaches have nice sand that packs wonderfully and you can just cruise along. similarly once the gravel size gets big enough you can just cruise along, however there is definately a wide range of sand sizes that turns into the "evil sand" that
nothing packs it down and it's almost as bad as postholing in snow.