I am personally a big fan of trying to make character creation part of the game rather then just a bunch of math and book flipping done before you can start the story. When I ran Curse of the Crimson Throne I had each player undergo an in depth Harrowing amplified from the book which added a little detail about their past and danger in their future etc...
For Skull and Shackles I created a game called Besmara's Ante that helped provide some flavor and offer some shape to each PC with story attached. Basically the PC's all find themselves invited by a mysterious old salt to sit down and play a game of Besmara's Ante. They are told that playing this game will forever alter their fate. It is not for cowards. Then each player is given a set of four markers. Each set is a different color.
They take turns rolling the bones (2d6). They may roll them as many times as they want summing them up. The goal is to get as close to 29 as possible without breaking (hitting 30) or rolling snake eyes. Players get to place their antes (their markers) on the board in the order of whoever is closest to 29. Those who bust go last (in the order they busted). If someone rolls exactly 29 they get a special reward explained below.
The board has six columns labeled in order: Kraken, West Wind, Old Salt, Compass, Man in the Moon, and the Lady. There are four rows labeled from top to bottom: Cradle, Cup, Cutlass, Cards.
Each player may ask the Mysterious man they are playing with one question like: what is the nature of the West Wind? or What gifts does the Lady have for me? The Mysterious man should answer in riddles.
The players then each place a marker on the board. After each person has placed a marker and received the "reward" for that play they roll the bones again for another round. There are 4 rounds in Besmara's Ante.
The only rule of placement is this: you can't have two of your markers in the same column or row. So you can't have two of your own markers in the Cradle or two markers under the Compass etc... This means it is possible to get blocked out of placing all of your markers if you aren't smart with your choices.
A roll of 29 exactly allows that player to make one swap of markers already on the board at the end of that round of antes. This means that the players whose markers are swapped swap their rewards. The swap must follow the placement rules - no duplicate markers in the same column or row.
At the end of all 4 rounds those players who have been blocked from placing all their markers are allowed to attempt to bargain with another player to make 1 swap of markers on the board following all the placement rules. If this swap opens up a space where the blocked player can place a marker then they may do so immediately. So there is a chance to get in at the last if your fellow players are kind.
The "rewards" of the antes should be flavorfully described and are a mix of good and bad game effects and roleplaying fodder. To keep the PC's from starting overpowered I often do only a 10 point buy in character creation. Try to mix up the pattern of reward placement to make it a little hard to predict, but consider the symbolism so that you offer the players some chance of reasoning out how they want to place their antes.
I interpreted the symbols thusly:
Kraken - Strength/Damage
West Wind - Dexterity/Dodge
Old Salt - Constitution/Survival
Compass - Intelligence/Skill
Man in the Moon - Wisdom/Insight
The Lady - Charisma/Mercy
Cradle - A trait you've had from birth
Cups - A habit, or superstition
Cutlass - A feat or skill
Cards - Something connected to luck or randomness
So "rewards" might be:
Kraken/Cradle - +2 strength
West Wind/Cups - Fear of enclosed spaces
Old Salt/Cutlass - Toughness Feat
Compass/Cutlass - Skill Focus Feat
Man in the Moon/Cards - reroll a Will save 1/day
The Lady/Cradle - +2 Charisma
etc... make sure to sprinkle in enough bad things to make it interesting and to make swaps desirable. Choose feats and skills and such that suit your cast of characters. And have fun!
We play our games at my friends house. He built a Tiki Bar in his kitchen called the Sunburned Penguin so I'm going to turn it into the Formidably Maid for a night. Then I'm going to randomly hand out campaign traits. Then I'll pass them a drink to drown their sorrows and make them roll characters but keep them to themselves so that in the early part of the adventure they're all alone.