Somewhere between 5 and 7 is a good level. Have a nice stock of Potions before hand. Steal from the Sea Lion until you get the Mythril Dagger, then wait for Trance and heal as necessary. Use Tidal Flame to kill the Sea Lion, then attack Black Waltz normally.