It's usually called Prelude and you are correct DK it is a tradition in many FF games to have it. The battle with Gilgamesh (much later) song is also from previou FF games "Battle on the Bridge".

I thought no one could defeat that Mimic Queen at Barheim under level 10 but several people on this thread did it. How they managed I have no idea, at level 10 it was a bit hard to me.

To answer tyour question, the mission on the Leviathan right after the Lhusu mines can be done at level 13, if you run away from the Lhusu Boss (SPOILER)Ba'Ganmaan and his gang but to defeat the boss you need to be around level 20 (that's how high I was). At level 13 the LEviathan ship gives some people trouble with the Boss, at level 20 the ship and it's boss where a cakewalk.

BTW, here is the ONLY map of Leviathan on the net, ripped by yours truly