A church may be constructed almost immediately upon landing on the shores of the New World. The population of a colony need only be 3. This causes increased cross production instantly. If you put colonists to work in the new structure, you can create even more. A church can be upgraded to a Cathedral.