Well, just got the airship. I have to say, I'm going pretty damn fast!
I never noticed that you can actually sequence break a lot once you get the fire-powered ship and later the black chocobo. That way I visited all the towns and got all the available summons even before I got the airships, which is pretty rad. At this point, all that's left is taking on the flying fortress and we're moving on to the second world!