In one of the pre-release screenshots for the game, one of the protagonists is seen diving a submarine among what appears to be the sunken wreckage of large crane and an industrial building. A further look at the area was seen in one of the game's trailers, causing many players immediately to assume that the underwater wreckage was a sunken city.
It is highly unlikely that the ruins shown in the trailer are of a sunken city, as it would be foolish of Rockstar to give away such a big Easter egg that early. The whole purpose of an Easter egg is for the player to find it on their own accord.
Upon further investigation, the underwater city was debunked as being false. The "city" is actually the wreckage of a freighter located to the east of East Los Santos. In the end, there was no sunken cities in the underwater region of the game.