Lethal Lissy

Throughout the city of Liberty Bay. To the northwest of the city will appear the boss Lethal Lissy.

Deadeye Devious

Next to the Depot, the boss Deadeye Devious

Brutus Bloodbeard

Next to the ladder that leads to the boat, the boss Brutus Bloodbeard will appear.

Ron The Ripper

At Liberty Bay Fort, boss Ron The Ripper will appear

Hope this helps.
They always appear on the second warning. I'm used to it :p