For some reason, I've always had it in my head that a windwright captain would have so much control over his airship that he can flank with it.
I can't remember if its a druid alternate class feature or a full on prestige class, but something allows you to have an elemental as a companion. Once more, throw that puppy into the crystal powering the ship, and look, treeships.
Back to the legendary captain debate, you have to think about what the campaign is going to be about. Will you be flying against other airships? are airships going to be a dominant part of the story? will you have to leave your ship for extended amounts of time?
Really, Legendary Captain is only good if you're to be staying with your ship most of the time. However, if you want to be a captain of the ship but still do some dungeon crawling, convince the dm that you should be able to have a cohort that is as high of a level as you. When you're on the ship, you control the captain and the dm controls the cohort, and if you want to leave the ship, you seek treasure with the cohort and the dm controls the captain and the ship.