Ideally, Muslims should treat Christians in Muslim-majority lands the way they want Muslims to be treated in Christian-majority lands. The following fatwa by the widely respected Islamic scholar Shaykh Yusuf al-Qaradawi finds it unproblematic for Christians to build churches in Christian-majority villages and cities where they have a need for it. He also supports the right of the leader of the Muslim community to judge church-building in Muslim-majority areas on a case-by-case basis, allowing it when the good of the public, both Muslims and Christians, is served by it.
Beginning of Translated Fatwa from IslamOnline
Islam requires non-Muslims to respect the feelings of the Muslims and the dignity of their faith, so that they do not put their religious symbols and crosses on display in Muslim cities, and so that they do not build new churches in Islamic cities where no church existed before. These requirements are there because they challenge [the] Islamic feelings [of the population], which can lead to public discontent and trouble.
As for villages and places that are not of the Muslims [apparently meaning that they are not Muslim-majority], they are not prohibited from displaying their religious symbols, renewing their old churches and building what their needs require out of consideration for their increasing numbers.
In this question there are also other opinions, the crux of which is that it is permissible for the leader of the Muslim community to allow the building of new churches in the cities of the Muslims if he sees a public good in that.
Shaykh Yusuf al-Qaradawi says:
Islam protects the places of worship of non-Muslims and respects the dignity of their religious symbols. In fact, one of the reasons that the Quran uses to justify fighting is the protection of the freedom of religion, as God says: ”
Permission is given to those who are fought against, and God is Able to give them victory.
Those who were unjustly evicted from their homes, merely for saying, “Our Lord is God.” Were it not that God repels people by means of others: monasteries, churches, synagogues, and mosques—where the name of God is mentioned much—would have been demolished. God supports whoever supports Him. God is Strong and Mighty. (The Quran, verses 22:39-49)
We have seen how the treaty of the Prophet PBUH with the people of Najran mentioned that they enjoy God’s closeness and the Prophet’s protection on their properties, practices of faith and places of worship.
The treaty of Umar b. al-Khattab to the people of Ilya’ (Jerusalem) mentions their religious freedom and the dignity of their places of worship and religious symbols:
This is what God's servant Umar, commander of the faithful, bestowed on the people of Ilya' of safety and protection:
He gave them safety and protection for their selves, their properties, churches, crosses and all the rest of their items of faith (millatiha). Their churches shall not be inhabited [by Muslims], nor shall that be demolished nor reduced, nor anything within their perimeter, nor their crosses, nor their properties. They shall not be forced out of their faith, nor shall oppressive acts be carried out against any one of them. Nor shall any Jew inhabit Ilya with them. (As mentioned by al-Tabari, Egypt: Dar al-Maarif, vol 3, p. 609)
In Khalid b. al-Walid’s treaty with the people of Aanaat there is:
They may strike their church bells at any hour they wish of the day or night, except during the times of the formal Islamic prayer, and they may march with their crosses during their religious festivals. (Al-Kharaj of Abu Yusuf, p. 146)
All that Islam request of non-Muslims is that they should respect the feelings of the Muslims and the dignity of their faith, so that they do not put their religious symbols and crosses on display in Muslim cities, and so that they do not build new churches in Islamic cities where no church existed before.
But some Muslim jurists allowed the people of dhimma (non-Muslims living under a Muslim constitution) to build churches and abbeys and other places of worship in Islamic cities, and in countries conquered by Muslims after fighting (meaning that they did not peacefully surrender). The leader of the Muslims allowed them to do that [to build new churches], based on consideration for the public good, as Islam continued to respect their beliefs.
The Zaydis and Imam Abu l-Qasim (of the disciples of Imam Malik) had such an opinion (see Ahkam al-Dhimmiyyin wa-l-Musta’minin, p. 96-99).
It appears that this is how things proceeded in history of the Muslims from an early period. In Egypt a number of churches were built in the first century of the hijra, such as Mar Marqas [?] in Alexandria between 39 and 56 AH (659-660 CE to 675-676 CE). The first church in Fustat was built in Haarat al-Rum, during the governorship of Mukhlid between 47 and 68 AH (667-668 to 687-688 CE). Abd al-Aziz b. Marwan, when he founded the city of Hulwan, allowed a church to be built in it. He also permitted some bishops to built to abbeys.
There are many other examples. The historian al-Maqrizi mentions in his book al-Khitat many examples, then he finishes by saying, “All of the aforementioned churches of Cairo have been built during the Islamic period, there is no debate on this.” (See Al-Islam wa Ahl al-Dhimma by Dr. Husni al-Kharabuti, p. 139, also see The Preaching of Islam by Thomas W. Arnold, p. 84-86, third impression. Translated by Hasan Ibrahim and his colleagues.)
As for villages and places that are not of the Muslims [apparently meaning that they are not Muslim-majority], they are not prohibited from displaying their religious symbols, renewing their old churches and building what their needs require out of consideration for their increasing numbers.
This tolerance toward those who differ in religion, from a nation whose entire life was built on religion [i.e. the Muslims], after they were victorious and conquered, is something that the history of religions has not seen before, and the Westerners agree on this.
The great French scholar Gustave Le Bon says:
We have seen in the verses of the Quran that we have mentioned that Muhammad's tolerance toward the Jews and Christian was immense. Founders of previous religions did not have such a policy such as those of Judaism and Christianity. We will see how his successors continued in his tradition.
Certain skeptical European scholars, and the few Muslims who have deeply studied the history of Arabs, have admitted this tolerance. The related statements from many of their books show that our opinion in this matter is not unique to us. Robertson says in his History of the Reign of Emperor Charles V.:
The Muslims alone combined between zealous religious faith and tolerance toward the followers of other religions. Despite their eagerness to spread their religion, they allow those who were unwilling to convert to follow their own religious teachings." ([mentioned in a ] footnote on page 128 from the book The Civilization of the Arabs by Gustave Le Bon.)
And God knows best.
End of translated fatwa