I've decided that the characters will start out around level 4 for this game. I'll likely just have the players roll stats down the line (switching one pair as they like) as usual, then give everyone a set amount of XP (10,000 seems good) and they can level up to whatever that makes them.
Each character will get to roll d4+2 for starting potions and scrolls (I'll have a short-list of what they can choose from). Then they consult this chart:
Character Creation Customization.
Choose or roll 1d10:
1. magic weapon (type chosen by player, bonus by DM)
2. magic armor (type chosen by player, bonus by DM)
3. magic wand (type chosen by player, charges by DM)
4. miscellaneous magic item (chosen by DM)
5. extra 1d4+1 potions and/or scrolls (chosen by player, up to L3 spell scroll)
6. captain (small sailing ship, small galley, or longship)
7. 1d6+2 followers (0-level NPC men-at-arms)
8. henchman/cohort/sidekick (2nd level NPC, class chosen by player)
9. special mount (up to 6HD creature)
10. aristocrat (have land holdings and titles on mainland, +1d4 x1000gp)
I'm also considering the possibility of making any PC with an 18 in any ability to be considered a 'demi-god' of the mythic Greek variety, with an immortal patron and immortal trying to hinder the hero's progress. Then again, the players want a more Victorian pirates type thing than the Greek mythology thing, so I might drop this.