Kevon,

I won't recommend a shoe or sandal, I think those have all been covered, but I will recommend a sole. From my military days, we would have our boots resoles with sand soles.
Hopefully my picture shows. Sometimes these soles are called ripple soles. You don't have to buy shoes with them, just take the shoes you want and have them re-soled on. Most cobblers I have seen have them in stock. I will finish with this, they make a BIG difference when walking in loose sand.
_________________________
I've taken a vow of poverty. To annoy me, send money.