On a certain continent, nearly all kingdoms worship under the same pantheon. However, in the southern reaches the peoples take a much more...liberal stance on their Gods. Statues are nude, and very anatomically correct, and icons are often startlingly brazen. For instance, the icon of (insert name), the goddess of love, is an image of two nude twins embracing in a passionate kiss, signifying the love of both family and partner. This is a source of unending outrage and offense for the Northern churches, whose traditional and modest take on religion is constantly at odds with the near-blasphemous ideals of the Southerners. While this is not enough to provoke outright conflict, there is more than enough simmering discontent and long-held grudges between the two hemispheres.
Pirates' many bejeweled rings and piercings actually had a practical purpose - when the pirate or sailor died, the rings could be taken off as payment for a proper burial, saving him from a watery grave. This could be tied into regional culture, or made into a quest (The Pirate's Lost Rings, etc.). Also gives treasure-seeking divers another thing to look for besides crusty old chests.
The PCs are accosted in a major city containing at least one famous fortuneteller / prophet of the future. They are informed that their as-yet-unborn child will (insert terrible evil), and that, although they are very sorry, the PC must be executed to keep this from happening.