You're asking a worldwide question that covers literally every shoreline in the world for a period of thousands of years. I'm unfortunately not able to speak with that kind of breadth, so I'll focus in on two areas: Beringia and the Black Sea. If you are interested in learning more, I'd suggest picking up a copy of Prehistoric Archaeology on the Continental Shelf: A Global Review, which contains a collection of articles from around the world on this exact topic.

The Last Glacial Maximum peaked between about 26,500 years ago. As its name indicates, this was the peak of the last ice age. In the Northern Hemisphere, the great glaciers began to disintegrate about 19,000-20,000 years ago, and the melting of the West Antarctic Ice sheet between 14,000-15,000 years ago really accelerated the rise of global sea levels. There's a lovely 2009 paper in Science that takes a global look at the subject if you're interested in details about the LGM.

During the LGM, sea levels retreated (as you noted in your question). In my stretch of the world, this created a territory known as Beringia, which includes Alaska, the Yukon, Kamchatka and the Chukchi Peninsula. This "land bridge" connected North America and Asia and is believed to be the principal route for human migration from Eurasia to North America.

Now, the concept of a "land bridge" is somewhat of a misnomer, as we're beginning to learn. For much of the 20th century, it was believed that Beringia functioned exactly like a bridge: People would cross it to get from one place to another but not linger. It was thought that Beringia was a cold, windswept and bleak place.

In the last decades of the 20th century and the first decades of this one, that view has changed. What we've now seen develop is the Beringian Standstill Hypothesis.

Archaeological remains, pollen analysis and climate records show that Beringia was less cold and less bleak than we had previously believed. The area that is now the Bering Sea (north of the Aleutian Islands, south of the Bering Strait) may have had a climate similar to Siberia and Interior Alaska today. Brutally cold in winter, to be sure, but pleasant and full of life in the summer. Glaciers may have dominated what is now Canada, New England and the northern Great Plains, but they never touched low-lying Beringia.

This is an attractive idea for a lot of reasons. Not only does it explain some of the archaeological evidence in Alaska, the Yukon and Russia, it also may explain archaeological finds farther south. More and more, archaeologists have been finding evidence that the first humans in North America arrived much sooner than we had previously supposed.

The predominant theory had been that humans arrived about the time that the West Antarctic Ice Sheet was melting and raising sea levels. Now, it seems they may have arrived even earlier, possibly even before the start of de-glaciation.

If there is evidence of this, it could rest in the Bering Sea. Unfortunately, the Bering Sea (and strait region) contains some of the most inhospitable weather in the world. Furthermore, its remoteness means that any bathymetric archeological surveys would be extraordinarily expensive. In the 1960s, suspected stone artifacts were recovered off St. Lawrence Island. Further analysis showed they likely were created by geological processes. In 1976, archeologists performed surveys preparatory to oil drilling near St. George Island. The limited surveying they did do illustrated the problems of weather and logistics in the Bering Sea. They didn't find any archaeological remains.

In 2010, Michelle Ridgeway (Full disclosure: I've worked with her before) discovered a series of structures that appeared to resemble mollusk shell middens common to shoreline prehistoric archaeological sites. Those structures showed up on a sonar survey and need to be analyzed more.

Some better luck has been had in Southeast Alaska and off Haida Gwaii, where fishermen have actually pulled up stone artifacts. Given that these finds haven't come from recognized archaeological digs, however, there's not much we can gain from them.

When it comes to Beringia, it's not that we haven't even scratched the surface: We have barely even looked at it.

---

Now, let's travel halfway around the world and a few thousand years into the future, to the Black Sea and a time about 7,600 years ago. The Pleistocene epoch has ended, and the Holocene has begun.

At this point, the ice sheets have retreated greatly. Human beings have established agriculture, and the first cities are bustling in Asia Minor. In North America, the Laurentide Ice Sheet is melting fast and collapsing into the Atlantic Ocean and through the Mississippi River basin. Sea levels surge upward. In the eastern Mediterranean, the rising sea level washes across the Isthmus of Turkey. As it goes, it erodes the isthmus, and salty sea water pours through the gap and down to a lake that has ─ until now ─ been below the new sea level.

Now what?

In the 1990s, geologists William Ryan and Walter Pitman were among researchers performing bathymetric surveys off the southern coast of Ukraine. Along the ancient shoreline, they found large collections of freshwater shellfish shells that indicated the Black Sea had once been Black Lake.

Ryan and Pitman hypothesized that when this flood arrived, it did so rapidly. Here's a quote from their book, which they published in 1999 as Noah's Flood: The New Scientific Discoveries about the Event That Changed History:

"The level of the lake began to rise six inches a day, immediately inundating the deltas and invading the flat river valleys – moving upstream at as much as a mile each day, without pause hour after hour, day after day, drowning the less agile, forcing all else upriver or up onto the desertlike plateau through which the valley had been cut. It is hard to imagine the terror of those farmers, forced from their fields by an event they could not understand, a force of such incredible violence that it was as if the collected fury of all the gods was being hurled at them. They fled with family, the old and the young, carrying what they could, along with fragments of the other languages, new ideas, and new technologies gathered from around the lake."

Ryan and Pitman suggested in the book that this flood, this Black Sea Flood Hypothesis, was the origin of so many of the flood stories that show up in ancient religions (including the Old Testament). They further suggested that the flood forced lowland farmers upland and contributed to the spread of farming across Europe.

Naturally, such an extraordinary claim met a huge amount of pushback.

At the time, Ryan and Pitman were seen as overreaching. There was little evidence to support the idea that the flood happened rapidly, or that it spurred the spread of farming.

Soon after the book was published, a team including ocean explorer Robert Ballard made a remarkable find off the northern shore of Turkey. His expedition discovered what appeared to be paleolithic settlements along the ancient shoreline. Ballard's group was much more cautious than Ryan and Pitman had been, but the National Geographic Society (which partially funded the survey) wasted no time in claiming that Ballard's group had found evidence that Noah's Flood actually happened.

In the years since Ballard's find and the Ryan/Pitman book, plenty of geologists and archaeologists have suggested the flood happened much less quickly or was less extensive than Ryan/Pittman suggested. A January 2009 Quaternary Science Reviews paper, for example, suggests that Ryan/Pitman goofed on the level of the lake when the flood happened, which would make its rise less severe. Other papers have argued that the lack of neolithic settlements in modern northern Turkey isn't because they were flooded. Still others argue that the spread of farming throughout Europe was driven by the migration of people all over, not just from the Black Sea region, as sea levels rose.

In any event, the Black Sea is a particularly ripe area for marine archaeology because anoxic conditions (no oxygen) preserve organic artifacts. There are huge numbers of preserved historic shipwrecks (including from classical Greece, the Byzantine Empire, the Roman Empire, and the Ottoman Empire) awaiting to be explored.

Unfortunately for your question, prehistoric archaeology just isn't as sexy as historic archaeology. It doesn't get enough funding to explore even the most basic aspects of life in prehistory. Why? Well, just look at the question queue around here. How many questions do you see on prehistory? How many do you see about knights, tanks, or Hitler's moustache?

Fortunately, if you do have an interest in prehistory, there's no shortage of opportunities for you to make a find of your own ...

I don't know from prehistoric times, I'm afraid, but I can answer your question about the Mediterranean and Asia Minor.

There are several settlements in early historic time whose locations are now either submerged or that were abandoned because of coastal silting. Tartessos (possibly the biblical Tarshish) is the largest example I can think of offhand. In the vague area where we know it to have been we have made some finds.

On the other side of the Mediterranean, in fact in Egypt, well within historical times a good chunk of the old city of Alexandria went underwater. You can, if you want to, take a scuba tour of the streets Cleopatra may have seen from her sedan chair on the way to Caesar's ship. With some poetic license available.

There are a number of lost cities, as you seem to know, and a good number of them were coastal, or perhaps along rivers. Some of them seem to be located along the northwestern coast of India. Trade routes in the late Bronze Age were fairly good (or, at least, better than they'd be for another few thousand years) between the Phoenician coast and the western Indian deltas. Tales could slip back and forth repeatedly and end up so muddled that no one knew which end they'd come from.

More direct to your question about the start of civilization, The problem with finding prehistoric evidence is probably the same everywhere on Earth. When we do find Neolithic sites, they're usually very isolated. Or they're sites that have been continuously occupied or were occupied for very long stretches of time. There are exceptions, and wonderful exceptions, but it's important to keep timescale and human nature in mind.

Stonehenge was being added to millennia after it was begun, and also modern man has been happily taking it apart for parts for almost as long as we've known about it.

An underwater site would resolve some of these problems, while adding the crushing difficulty of finding them underwater. We have, in the past two hundred years, lost a number of fairly large ships in fairly well charted water. In the past couple of decades, we've lost a number of planes in same. As the Alaskan said far more expertly, this a worldwide thing that would entail a time period of thousands of years. And as I've said, even when we know about a city and its general location from that long ago that doesn't mean we can find it. Ask a historian of Mesopotamia where, exactly, Akkad was.