"If the public land is the land between hightide and the water, shouldn't the public land be underwater during hightide by definition?"
Typically, there is some sand on the beach above the high tide line ("public dry sand easement" in zoning parlance). You're allowed to walk on this sand.
This isn't the case on Broad Beach or Carbon Beach. At either of these beaches, there is no sand at all above the high tide line. Just a large seawall of rocks.
Seems kind of like a problem for everybody, not just the people not living there. Granted, the people living there can retreat to their homes while other people have to walk/drive home I guess, but it seems like basically a shitty deal for everyone. The only "defacto-private" thing in this situation is a shitty rock wall.
The homes of the people living (or the rock wall) there are probably the cause of the lack of beach.
Beaches are dynamic things, they get eroded during storms and are built up at other times. They can recede inland hundreds of metres over the years. Conversely, large amounts of sand can be deposited, extending the land well out into what used to be water.
Humans putting houses, sea walls, groynes, bridges and other structures along the coast conflicts with the natural movements of the coast. In this case, if the houses were located further back from the beach, there would still be a beach there.