Baltor is a Black Pirate that is like any other - stealing from any ship in the sky, especially merchant ships. You will have to face him when guiding the Nasrean merchant back to his homeland. He was in the original SoA but not as a bounty. He is one of the two bounties that are an absolute part of the story. When you fight him, use repair kits when needed, or sacri if you don't have any. The best time to attack is C! (Critical on the grid) and use your cannons.
These are people who attack non-Nasr ships. Rupee is actually the small child in the picture to the left. His body gaurd is Barta, the big guy. You can find them on the pier closest to the stairs to the town of Maramba. I suggest you don't fight them until coming back from Yafutoma. Even though all bounties level up as you do, the Prophecy will come in handy, and especially some Riselem Crystals that can be bought from the Item Shop in Yafutoma. You'll want to have some really good Super Moves to beat them. Make sure you save and are at full health before you fight them. When fighting, don't try to use any spells to cause affects on them, but use spells on yourself, and possibly spells on enemies to attack them. Legendary Charge builds up spirit and Legendary Punch is quite painful to the character. Rupee usually uses magic, but watch out for Berserk Rupee! This can get tough so do your best to keep everyone alive and use the Prophecy and your best moves.
Gordo is a bit strange. He is a Black Pirate that only steals food from any vessel in the sky rather than gold. He can be found in North Ocean and can be accessed automatically because he is part of the story, the only other person that was in the first SoA that is now a bounty. He will board your ship for a hand-to-hand combat battle. He isn't very hard. First take out the 3 Mad Chefs with spells and attacks, then go for Gordo with Cutlass Fury or Drachma's tackle. If Vyse has Pirate's Wrath yet though you probably won't, that will work too. When you see him drinking Loqua, that means that he is preparing his super move, Loqua Spray, for another turn. This won't be too hard at all.