For the first time ever, I chose a different name from my first and only online game name of Griphos. This is the game I've waited for for. The age of sail is a deep and long held passion, so I wanted a name that fit. When I first joined the forum, one of my favorite characters in the O'Brian series came to mind. I thought I'd probably change it once I got the game.
I love names that just invoke the sea generally, such as Leviathan. I thought of names that just invoked ships themselves, such as Chainplate, or Hawsehole. I thought of fictional figures like Billy Budd or Disco Troop or Odysseus. I thought of historical figures, particularly privateers (my likely open world role interest) such as Jean Lafitte, Sam Reid, or Black Sam Bellamy.
In the end, it was a toss up between staying with Mr. Pullings and Black Sam (the Robin Hood of pirates). I couldn't decide, but I know that the fictional Tom got to captain the HMS Bellona, one of the most beautiful and best sailing ships in the game so far, so I just stuck with him. I think of his fictional character as an inspiration in some ways.
There's lots of great naval names left to use. Do a little research and you'll come up with a good one.