My latest idea is something I just thought of off the top of my head: Skyway Dungeons. Entire skyways dedicated to a single (technically single) dungeon. You would go around sinking ships and killing enemies, going through an island or two to get keys and magical things until you finally get to a final boss fight. It could either be against a huge boss like Scylla, or a powerful ship boss, or you could dock at an island with a normal boss on it.
Ooh, and cheats. Lots and lots of cheats.

Maybe those huge Tori Gates in Hamamitsu could be hiding a skyway dungeon- and, if this is ever added into the game, then most definitely the huge factory in Valencia would be one. I can imagine it already... it's only a little intimidating.