If you bring both Strago and Relm to Thamasa, you'll see a cutscene where Strago's friend Gungho convinces Strago to go after Hidon at Ebot's Rock. This also opens the entrance to Ebot's Rock. Note that while Strago mentions that Hidon won't show himself unless he goes alone, this is not accurate. Strago does have to be with the party, but you can (and should) bring other party members as well. Relm is not required for this dungeon.
Ebot's Rock
The layout and progression of Ebot's Rock are mostly random. You'll start off in the Entrance area. Every time you step on a floor switch, you'll be teleported to a randomly determined room in the dungeon. The first teleport is not random, and will take you to the Hungry Chest Area to establish the rules of the dungeon. You'll need to collect pieces of Coral to feed the chest in order to pass by it and find Hidon. There is one other room you'll often see, the Save Point Area.
Most of the time you'll be teleported to a Random Area. There are several of these, each with different layouts. They have differing numbers of chests, each of which contains 1, 2, 3, or 5 pieces of Coral. Your goal is to obtain 22 pieces of Coral, then feed them to the chest all at once. This total is not cumulative, so if you feed the chest 21 pieces of Coral, you'll need to go back and get 22 more. The game doesn't show you how much Coral you have, so keep a count. Also remember that the chest won't let you pass at all if Strago isn't in the party.
Encounters
There are a wide variety of Monsters in Ebot's Rock, and the Encounters are different in the Random Areas than everywhere else. In the Entrance and other special areas, you'll run into several mixed groups. The only homogeneous battle is against two Slatters. They open with their ×1.5 damage Choke special, then use normal attacks for two rounds before reapeating the process. They have a weakness to Pearl but no other notable traits.
Slatters sometimes also appear in the company of a Warlock and Eland. Warlocks spend most of their turns attempting to drain MP with MagicDrain, though they won't succeed until they've cast Pearl at least once. They have a chance to do this every other round, and it deals significant damage. Left alone on the battlefield, they will start casting Pearl exclusively. They are vulnerable to Thunder, as are Elands. Elands rely on basic attacks and can use Stench to Muddle your Characters. They have nearly double the HP of Warlocks.
Sometimes you'll find a Warlock with two Elands and two Clucks. These chicken-lizard Monsters can use Lick to cause Petrify. Never leave them for last, as they may use Quake. This may finish them off as well, but it will deal over 1,000 damage to any Character not protected against it. Clucks are vulnerable to Ice and absorb Poison.
The rarest encounter in the special areas of Ebot's Rock is against three Clucks and a Hipocampus. Hipocampi will counter Magic with Acid Rain, and other attacks with Flash Rain. Acid Rain is the weaker of the two, and combined with their undead vulnerabilities to Fire and Pearl, Magic may be the weapon of choice against a Hipocampus. Their normal attacks are nothing to speak of, and their Clamp special causes Seizure. With only 82 MP and the Wound at 0 MP attribute, Rasp is another effective mode of attack.
The Encounters in the Random Areas of Ebot's Rock are significantly different. You may occasionally see a trio of Hipocampi, but you'll usually see one of two new enemies. First is the Opinicus, which can appear in a pair or alongside a Hipocampus and an Eland. These Monsters will attack normally for three rounds, but attack three times (including once with Riot for 1.5× damage) in the fifth. They also counter Magic with Wind Slash. They are undead, so hit them with Fire or Pearl if you're willing to risk the counterattack. Otherwise, physical attacks and special Commands should be sufficient to defeat them before they go berserk.
Finally, there are Displayers. These giant undead monstrosities use ChokeSmoke, but they only target living Characters with it, so it's no threat. Their normal attacks and double-damage Rib attack should be easy enough to deal with. They have a lot of HP but the usual undead vulnerabilities to Fire and Pearl and no counterattacks.
Hidon
Once you've collected 22 Coral and satisfied the chest, you can approach Hidon. It is accompanied by four Hidonites, each one with its own unique Attributes and special attack. Your main goal here, and the primary reward of Ebot's Rock, is to have Strago learn GrandTrain from Hidon. This is the only battle in which this is possible, so don't finish it until Hidon has used it. He will not do so until all of the Hidonites are defeated.
All four Hidonites follow a similar pattern. They can use their special around half of the time, but will usually rely on basic attacks. They can also counter with these basic attacks. Each has 3,500 HP, but different vulnerabilities. Starting from the top right Hidonite and moving clockwise, here are their capabilities. The first is undead and thus vulnerable to Fire and Pearl. Its Zombi Claw causes the Zombie Status. The second Hidonite is vulnerable to all eight Elements and has the Safe Status, so is best dealt with magically. Its Mega Claw deals quadruple damage. The third Hidonite absorbs Poison and is weak against Earth. It causes Poison with PoisonClaw. Finally, the fourth Hidonite has a permanent Reflect effect, absorbs every Element except Earth, and uses Confuclaw to inflict Muddled.
Hidon itself is vulnerable to Earth, Fire, and Pearl, but absorbs Poison like other undead. Since Earth is the only Element that works on all five Monsters, Quake is highly effective here (but make sure the party is Floating so you don't kill yourself). It also bypasses the lower-left Hidonite's Reflect Status. Hidon can counter any attack with the Poison Spell, and as long as there are any Hidonites alive, it will stick to basic attacks and Bio. Hidon has the dubious honor of being the only Monster in the game that uses ChokeSmoke effectively. If any Character is Wounded, Hidon will use ChokeSmoke to turn them into a Zombie.
Once you defeat all of the Hidonites, Hidon will use GrandTrain for over 900 damage to each party member. Make sure Strago is in a condition to learn it. Approximately 80 seconds later, Hidon will bring all four Hidonites back to life. Until then, it will start attacking with Virite and Raid.
Once Hidon is defeated, Strago and the party will return to Thamasa and regale Gungho with tales of the battle. If you want to challenge Hidon again (perhaps because you failed to learn GrandTrain), keep speaking to Gungho in Thamasa. Every time you enter the town, there is a one in eight chance that he'll mention that Hidon has returned, and you can return to Ebot's Rock to challenge it again. You don't even need Strago in the party to trigger this event.