Fly to Cave
This procedure will allow you to gain two powerful Call spells for Rydia. Fly to the Northeast section of the underground to find a small island with only a cave.
Inside the Cave
The first thing to do when you enter the cave is to have Rosa cast the Spell "Float" on your whole party (you can do this all at once). This will protect you from the spots on the ground that damage your party and also from monsters that attack using the "Quake" spell. When you enter the cave go south, then immediately west until you reach another cave.
B2F
You will have to recast the "Float" spell again, because as you change floors, it is removed. In the next room, go right, then up and to the right down to the next floor. In the next room, follow the path until you get the opportunity to go north. When you reach that point, there will be a small grey staircase to take you into the Monster's lair.
Queen Asura
Go north, then east and take the first staircase you come to. On the next floor head around the outside circle of the room counterclockwise until you reach a building which has a chocobo stationed in front of it. Go into this building, then down the staircase on the left. Finally, go down the grey staircase in this room. In this room speak with the woman in the middle. She is Queen Asura and she will fight you.
Defeat Asura
Defeating Asura is not too difficult once you realize that you must have Rosa cast the Wall spell on Asura in order to make her cures ineffective. Once you have done this, you can simply attack as normal, remembering that you cannot cast spells directly on Asura or it will reflect back to you (Call spells excluded).
Defeat Leviathan
After defeating Asura, speak to the man next to her who you will learn is Leviathan. Battling him is a little tougher. His wave attack is pretty powerful. Your best bet is to have Rosa use Cure4 on the whole party after each wave attack. After defeating Leviathan he will give Rydia a spell allowing her to use his attack.
Exit Cave
Exit the building, then go back down the grey staircase. Head clockwise around the room until you are as far south as possible in the corner there is an invisible button that will take you to a room with four chests. Immediately behind where you are let into this room is a button that will allow you to exit the cave quickly.