And while I'm at it, (I'm bored) here are some boss ideas
Aforementioned Pirate Captain, we have to hire ships and stuff to go from island to island gathering the resources to intercept a raid he is making on a town and take him down in a duel Ground/Naval where the entire floor is his dungeon
The Chessmaster/The King, shaped like a King from chess, we literally need to beat him in a giant Chess Game, where we are pawns and to take out other troops we need to literally fight for control of a square on a board, basically the entire floor is a chessboard, and each grid thing is a town, and one of us has to coordinate out movements while Chessmaster does the same with his minions
A giant worm thing; I know, it's overused, the big worm which turns into two smaller ones once a segmant is destroyed, but it is quite interesting, especially if fighting it in underground caves where the tunnels IT leaves are our only ways through the world. Imagine it attacking us and one of us accidentally breaking it into two, so now we can split into multiple groups to hunt down smaller and smaller segments
A giant mole: same basic premise as the Worm, but much more dangerous as it has minions and better control of where it is going
The Rat King: a once prosperous land overcome by rats eating everything and causing severe famine, now extremely hungry rats (who never seem to starve to death) inhabit the abandoned towns, lead by a really fat rat with a nigh-infinite amount of rats to do its bidding, which lives in the old capital city, which has also been overrun by rats.
I know none of them really come from anywhere, like King Minos from the Greek Legends, but still