"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.