It's a very basic story: Rulers of a land find access to power (the Sunstone, red rock) and they use it to bring peace and serenity to their kingdom (in this case, they even make it float), through this power comes great technology and through this technology comes information of a new power source, seemingly better. They find a way to harness this power source (Mammon Machine) and it turns lover against lover (Zeal and her husband). Zeal thirst for the power of Lavos, her husband tries to save her from herself and is squashed in the process. Hell, she could have even found a way to talk to Lavos, who knows. Perhaps she got the notion for Immortality in her head all on her own. For whatever reason, she got it. She didn't intend to share it, but knew that she had to promise immortality to her subjects for them to help her obtain her goal. When the Ocean Palace is finally constructed (so Zeal could get closer to the source of Lavos) She uses Schala and the Mammon Machine to waken Lavos and get his attention. At this moment, Lavos senses Zeals thoughts, probably decides then and there to take her under his wing because they can further each others aims (i.e. Lavos gives Zeal immortality and power and a new floating palace and Zeal help Lavos obtain energy faster than he's transferring it to her). Whatever the case, The Ocean Palace becomes the Black Omen when it rises into the sky with Lavos' power. before that happens though, I'm sure he sensed the animousity coming from those in his vicinity: Crono and Crew, Magus/Janus, and the Guru's. Seeing the Guru's as little more than an annoyance, he splits them up and sends them through time, along with the unintended Janus child. After this, he decides that a show of power is in order for Crono & crew and subjects them to an unwinnable battle, whereupon Magus attacks and is met with much the same fate.
I think that at this time, Crono was about to unleash a power that would completely decimate Lavos' Shell. A last-ditch effort of some sort. Sensing this danger, Lavos unleashed a highly focused energy shot which should have killed him, but didn't due to the interference from Crew at the top of Death Peak in 2300 AD. Now, after having thought he set THE example for them and wouldn't be bugged again, imagine his surprise to find them aboard the Black Omen when Zeal calls upon him, and to find that they bested Zeal, to whom he gave untold power to. bit of a shocker, if you ask me. But, Lavos probably figures, OK, I took care of this once, and I'll do it again. Zeal has outlived her usefulness at this point and The Black Omen is destroyed in that instant, and Crono and Crew are once again brought before Lavos' Shell to be dealt with, but he got more than expected. He got beaten.
You can't beat The Black Omen in 2300 AD. You fight the defense lasers and then Zeal comes and tells you that it is simply too late, but if you go to 1000 AD and fight it, the defense lasers are already taken care of, and if you beat it there, the Black Omen itself is still in the other area's, but I think all the treasures aren't there anymore, and I know it's just a skeleton crew of monsters on board. Whether this is because Zeal and Lavos transcend time altogether, which is believable, except for the fact there is no Black Omen in prehistoric times and the fact that it would make Lavos Immortal himself, and thus unnecessary for him to collect the Life energy of the planet. as for that matter, I dont think Zeal was immortal either. Granted a life as long as Lavos' or pretty close to it as long as she served him, but it could be taken away at his choosing, but not immortal. I think, in this last part, it was a ploy used by the developers of the game to conserve space on the game by making The Black Omen the same for all time periods it was in, except for when it was destroyed, giving you the option to destroy it in 1000 AD, 600 AD, and 12,000 BC. And except for the obvious exception of it being too late in 2300 AD. Though, I think that if you beat it in 12,000 BC first, it disappears from all other time periods, thus disproving the transcending time theory.
As for Terra Tower it could be that the Dragon God willed it to float, or it could be that the reptites had technology of their own, which is shown in Ayla's time period in CT with the T-Rex Azala constructed, and their fortress. That and Azala, while not knowing exactly what the Gate Key was, did know that it was highly technologically advanced, which is more than could be said for the poor primates, who probably would have confused it for a flower. And probably ate it. and Died. No, the reptites had technology of their own, too. If left to advance it, instead of being destroyed by Lavos, they could very possibly have created a floating fortress. it isn't beyond reason.
Placidchap: good question. the term magic WAS used in Zeal, but rarely. They referred to it more as an aura, but the term magic was not unknown to them. Aura being the more refined word for it, and magic being the more base word for it, not to be used among nobles, you know?