Religious pluralism in Europe was definitely much more common than people think. The common modern perception of pre-modern Europe is that it was basically non-stop persecution of religious minorities until the light of modern reason put an end to all that. Now, make no mistake, religious minorities often suffered persecution and violence, and, as far as I know, nowhere in Christian Europe would a Jew or Muslim be seen as equal to a Christian. Nevertheless, religious pluralism was a reality and people found ways to make it work.
In the Islamic world, there was a legal framework for the treatment of Jews and Christians. As fellow "peoples of the book," Jews and Christians in Muslim-controlled territories were legally tolerated as dhimmi and could practice their religion freely, in exchange for paying a special tax called the jizya. While this dhimmi status essentially made them second-class citizens, it did provide a stable legal status which allowed these communities to coexist largely peacefully with their Muslim rulers. Sarajevo, under the rule of the Ottomans from 1450s to the 1870s, was shaped by this legal context. Churches and synagogues could exist publically, although the prime religious real estate was generally reserved for Muslims. Religious minorities could still suffer persecution under Islamic rule, as the Jews did in the 13th century when the Almohads took control over the Islamic sultanates in Iberia, but their legal status was much clearer than it was in Christian Europe.
Because Christianity did not develop the same legal framework for treating religious minorities as Islam, things get a little complicated when examining the experience of religious minorities in Christian controlled lands. It was basically up to individual rulers to determine the status of minorities in their territories, which led to a lot of different systems, and often sudden changes in policy. I will give just a few examples to give a general picture of the different possibilities.
For much of the medieval period, Christian kingdoms in Iberia maintained, to various degrees, tolerance of Muslims and Jews. Throughout Europe, Christian rulers often protected religious minorities for their economic benefits. Most famously, Jews were not subject to Christian prohibitions, and became useful bankers. But that was just one example. Muslims in the Kingdom of Aragon received protection from both monarchs and nobles for their agricultural skills, and those of Granada for their skills in the silk industry.
There was also a religious reason for toleration. As the Italian jurist Marquadus de Susannis put it in his De Judaeis et aliis infidelibus (1558), Jews offered "proof of our faith from its [very] enemies." Jewish religion offered a contrast to Christianity and was often used for polemical purposes by Christian writers and preachers. Jews were subject to ritualized violence, with attacks on Jews around Easter commonplace, an expression of the common Christian view of Jews as Christ-killers. These tensions could boil over during periods of particular criseis, which is why so many pogroms took place during the years following the Black Death. But, laws forbidding intermarriage and mingling after dark demonstrate that relations between Jews and Christians could be quite friendly indeed.
As the power of European states grew in the 15th and 16th centuries, the status of religious minorities often worsened. A combination of increased state power with the belief that Christian states constituted a sort of "body of Christ" led to attempts to purify society in a variety of ways. The most extreme example was likely the forcible conversion of all the Jews and Muslims of Spain and their subjection to the surveillance and persecution by the Spanish Inquisition. Inquisitions were set up elsewhere in Europe as well, but forcible conversions were the exception rather than the norm. Italians shared the desire to purify Christian society, but, starting with Venice in 1516, opted to create walled neighbourhoods, or ghettos, for Jews. This allowed them to physically separate Jews from the rest of the Christian city, giving the appearance of purification. It also allowed them to continue highlighting religious difference for Christians since the ghetto was always overcrowded and contrasted with the splendor of the Christian areas of the city. Jews in Rome's ghetto were also subject to weekly conversionary sermons. That being said, ghettos allowed Jews to continue to practice their religion, in many ways more peacefully than before since the guarded walls protected them from attacks by their Christian neighbours.
The 16th century also brought the Reformation and unprecedented divisions within Christianity, leading to a whole new era of religious conflict and coexistence. On the one hand, Christian heresy posed a greater threat to religious purity; Christians could tolerate Jews on the grounds that they were stubbornly ignorant of Christian truth. A Christian willingly turning towards heresy was a different story, a fact which led to the terrible violence like the St Bartholomew's Day Massacre in 1572 in which Catholic Parisians (followed by their co-religionists in other cities) massacred their Protestant neighbours. On the other hand, these heretics were still fellow Christians and as such the Christian virtue of charity could be used to call for grudging toleration. So, the Edict of Nantes, which basically ended the French Wars of Religion in 1598, offered legal toleration for France's Protestant minority until those "who adhered to the supposedly reformed faith" could find their way back to "the true religion" (i.e. Roman Catholicism). Another innovative solution was put into practice by the Dutch Republic. The only publically recognized religion of the United Provinces of the Netherlands was the Reformed Church, but residents were granted "freedom of concsience" to believe and practice their faith in private. This allowed for the proliferaiton of "schuilkerken," or clandestine churches, hidden in plain sight essentially. One famous example is the church of Our Lord in the Attic, a 17th-century Roman Catholic Church that operated out of a canal house in Amsterdam. The government was well aware of such "secret churches" but tolerated them, allowing for de facto religious freedom in the Dutch Republic.
There's so much more that could be said, but I think you get my point. Religious coexistence in pre-modern Europe was not all sunshine and roses, but it was a reality, and Europeans of differing religions found ways of getting along.
Further Reading:
Kaplan, Benjamin. Divided by Faith: Religious Conflict and the Practice of Toleration in Early Modern Europe. Cambridge, Mass.: The Belknap Press of Harvard University Press, 2007.
Nirenberg, David. Communities of Violence: Persecution of Minorities in the Middle Ages. Princeton University Press, 1996.
Terpstra, Nicholas. Religious Refugees in the Early Modern World: An Alternative History of the Reformation. Cambridge: Cambridge University Press, 2015.
Walsham, Alexandra. Charitable Hatred: Tolerance and intolerance in England 1500-1700. Manchester and New York: Manchester University Press, 2006.