I am in Cool Ranch, now trying to fulfill all the silly Dan requests (I absolutely hate him!) to get to Sally. I have to sink Monquista ships. I have a Bison Frigate, but I CAN NOT shoot anything there down, same with the De Monte ships. WHY! There are no other ships stronger than mine to be bought yet, but they shoot me down like I was a paper doll, but I can go shink every Armada ship in Valencia without blinking an eye. What's wrong with this picture? This game has so many flaws it is ridiculous!
I'm not sure how much this will help since I don't remember the level of the bison frigate, but at level 24 you can get a marlybone skiff (lvl 26 hull) in port regal (you may need a friend with access to get there from the quests you describe), or at lvl 30 I think, you can get a bison Galleon (level 32 hull I think) in tumbleweed. The only other suggestion I can make is try to find others doing the same quests and swarm the ships you need.