Any suggestions? I read one faq that said they found it near Adlehyde but it doesn't seem to be there for me
Theirs a triangle shaped patch of water between Adlehyde and the Ship Graveyard and its only fought at that spot.
Use the spell curse to increase the random battle rate and eventually it will show up (avoid using the Courage and Water Rune summons) unless you want the boss to gain HP.
It too does seem random.
There was one day where I took an afternoon off, sailed all around that dark water, and came up with nothing.
Another day, I found Leviathan in about 15 minutes. I didn't use curse or anything.
I found there's a small circle of dark water to the South of Adlehyde. Just stay in that small circle and you should find her.
I can't find it either and I'm about to give up on it.
RPG Classics says it's found here and only here http://shrines.rpgclassics.com/psx/wa/images/levbattle.jpg
Yet in this video it's found on a different patch http://www.youtube.com/watch?v=33AvmIV8Nqw
...and I just managed to trigger the battle twice, in two different locations. One in the darkest water, and one in the lighter water.
So it IS random, and you DON'T have to be in the deepest waters.
^And now you just shattered the universe. Strangely, I never had problems with this so I always assumed I had the "sweet spot." Oh well...
I'll have yer sweet spot!