The Scar by China Mieville
Bellis is on the run because she was a former lover of Isaac in Perdido Street Station. She, like anyone else who knew him, has had to flee the city of New Crobuzon or get picked up for government interrogation after the unfortunate matter of the dream-moths.
She takes work as a translator on a trade ship bound for a foreign city. Then her ship is taken over by a group of pirates at sea. The pirates operate out of a great floating city known as Armada; all their captives must come back to Armada to start new lives with them in total equality – but no one can ever leave.
That’s great for the lowly cabin boy Shekel and even better for Tanner Sack who, like the other Remade chained in the hold, was intended for slave labor in a far-away colony. Both get viewpoints and Tanner Sack in particular, who has himself Remade again to become an amphibian, emerges as a good man and a patriot whose terrible experiences only serve to refine him.
However, Bellis hopes to go home someday and so she must pretend to fit into Armada’s world while seeking to understand its agenda and looking for a way to escape. Armada’s mysterious agenda is powered by the Lovers, the strange dual leaders of Armada, and it involves searching for a vast interdimensional sea creature to help them fulfill some ungodly purpose. Protecting and guiding them is Doul, an expert swordsman with the ability to manipulate possibilities. Opposing them, more or less independently from one another, are Bellis, a vampire lord of one of Armada’s precincts, and a manipulative spy for the corrupt government of New Crobuzon. Another vastly imaginative work.