The most logical choices for "new" characters would be making bosses/AI assist characters from the previous two games playable: Arlong, Wapol, Hatchi, Sentomaru, etc since they already have most of their move-set animations and designs programmed already. Blueno would be unlikely but most others shouldn't have much trouble. That was the lion's share of the new characters in PW2 and they seem to be following the same pattern in PW3 though with somewhat more wholly new characters since PW2 relied heavily on asset reuse.
Also, the previous game had a serious lack of playable Zoans. Outside of Chopper, there really was only Marco. At least we're getting slightly more with the inclusion of Rob Lucci.
As for wholly new characters, why not Vander Decken? Very unique fruit ability that could make a good sniping character and some fun in hurling guys around. If they're going to do FI, that would be one of the more interesting characters to include. I'd also like to see more Baroque Works guys playable (including Mr 2 and Mr 3).