I'm going off of the assumption that all of the refrences to "10,000 years ago" in Chrono Cross refers to circa 12,000 BC. I'm also going to assume there's a lot more to the World Map than is apparent (otherwise Truce has a population of around a dozen, and the whole world less than 100).
Lavos crashes to earth in 65M BC and begins plotting. He wants to spawn his progeny around the universe, but he realizes the planet is his biggest foe, so he needs to set up guards against it. First order of business: kill all the Reptites through making the earth cold. However, the planet is powerful and is able to keep alive the timeline of the Reptite's survival, instead of them being tossed into the Darkness Beyond Time. Lavos realizes this and decides he needs a master race for his own use. He begins radiating power to evolve humans, so that they might one day do his work for him. In this original timeline, Zeal does not exist, nor does he cause the apocolypse, but he does guide/allow the construction of Chronopolis in 2400 AD. He causes the time crash and brings it back to him at the time most ideal for him: 13,000 BC. Humans are the far along in their evolution, but the Ice Age hasn't ended yet.
The Planet takes the bait. It sends back Dinopolis from the paralell timeline and they do battle. The Earthbound ones hide in their caves as a massive war goes on outside in the snow. Eventually, the Dragon God is slain, but Chronopolis is badly damaged too. The humans begin picking through the rubble of both sides, and learn some of the secrets of both. Some of the humans learn enough to be called Enlightened. They construct the Kingdom of Zeal using the Elements of the Planet and the Technology of the Future and call it "magic". Eventually Queen Zeal comes along and decides she wants more power, and decides to refurbish the ruins of Chronopolis so that she can use it for her own ends. She enslaves the Earthbound ones and sets them to tasks fixing up and rebuilding Chronopolis, which happens to be located under the ocean. However, this angers Lavos, as he doesn't want anyone near the Frozen Flame or to tax his power, so he destroys Zeal. He considers the entire saga of the Zeal Kindgom a "side effect" of combatting the extra timeline the Planet had been brewing.
However, destroying Zeal left Lavos somewhat tired, so he wanted several thousand years, and then he finally did what he set out to do in the first place: create a fertile haven for his children. This is the 1999 Apocolypse. He no longer had use for Chronopolis, as the Planet's other timeline had been defeated. The Lavos Spawn then went out over the galaxy. That isn't the end of the story of course, Crono & crew murked things up, as did Schala, but I don't have anything new to add to that analysis.
In summary: the Ocean Palace and the Black Omen are, infact, Chronopolis.
