If the group finds a ship to take them by sea, they will get caught in a tropical storm. And they will get shipwrecked off the coast on an island to the south of The Red Eagles' Roost. Where they will encounter the unknown natives of the deep.
The Island is a rocky volcanic formation, with very little life. It has not been explored by the Old World colonists due to it's violent nature.
If they party explores the Island they will find an entrance to the cavernous network of the deep.