Short answer: The Qur'an and hadith teach us to respect other people, regardless of what they believe. However, they do not give an equal place to all beliefs or practices.

Long answer: While the Qur'an and hadith recognize several different religions, including Judaism, Christianity, and Zoroastrianism, they do not recognize the custom of worshipping idols in Mecca or Medina as a distinct religion.

As for whether the Arabs who worshipped idols in Mecca and Medina saw their customs as a distinct religion, it is difficult to say for sure, but there is no indication in the texts that they saw themselves as united as a single faith community or a single religion; appealing to idols was simply customary practice. They focused on tribal and ancestral identity, not religious identity. I am fairly sure that the term "wathaniyyah" was adopted after their time. In contrast, the Qur'an encourages replacing ancestral/tribal identity with a faith-based identity.

The concept of "religion" as we have it today (and as it is used in the English language) is rather modern. In fact, it is heavily rooted ins secularism. Everyone is expected to follow the same way of life (national culture, national laws), and religion is seen as a private matter. Therefore, we should respect everyone's personal decision about their religion (that is, private beliefs); however, everyone must follow the same way of life (national culture and law). So, in essence, national culture and law has taken the place of religion in modernity in most nation-states. 

In fact, many languages historically have not even had an equivalent word for "religion" as it is used in English today. 

So, talking about religions during the time of the Prophet Muhammad (S) or the Prophet Ibrahim (A) should be done with the understanding that we may be accidentally projecting modern ideas onto the past, or onto other cultures, and then trying to avoid that.

The Qur'an, hadith, and classical Islamic literature tend to use words such as din, millah, and shari'ah to mean "religion". These could be translated as "way of life", "community", and "religious law". From this angle, the communities that were identified as having a specific way of life, scripture, communal identity, and law were Jews, Christians, Sabaians, or other established communities. 

For instance, in the classical model of the Islamic state, certain religious communities (in particular, the Ahl al-Kitab, including Jews, Christians, and some others) are allowed to follow their own religious law, abstain from military service in exchange for paying the jizyah, and enjoy protection of their houses of worship. [Of course this model is somewhat theoretical as what happens in practice tends to be more complicated, but this is how things were seen theoretically]

However, neither the polytheists of Arabia nor the polytheists of the time of Ibrahim are seen as having their own communal identity based on religion or what we would call a "religion"; they are simply seen as (a) deviating from the truth, and (b) following common custom. 

Conversely, neither the Prophet Muhammad (S) nor the Prophet Ibrahim (A) is presented as a prophet bringing a new or alternative religion to his people (in the same way that, for example, Christianity was seen as a distinct faith community coming from outside the Arabian Peninsula). Both prophets are seen as supporting the ancient message, not bringing a new idea.

This is why the bulk of the arguments in the Quran are not about accepting Islam as a specific religion. Rather, it focuses on why the idol-worshippers (who believed in God as well as demigods) should stop appealing to their demigods and worship only God instead. That is, the idol-worshippers tended to worship their demigods to placate them, with the belief that if they did not, a disaster might strike them. Or they would worship their demigods to appeal to them for wealth or sustenance. Or, they would worship their demigods with the belief that their demigods would appeal to God on their behalf. The Qur'an, basically, says that all of this is unnecessary and/or false since all power belongs to God and their demigods do not control matters of good and evil or sustenance, and that their demigods are not really intermediaries. 

They should also give up backwards customs and taboos which are socially harmful and which were passed on along with their customs regarding idols.

For instance, Ibrahim (A) is not telling his people to follow a new religion; rather, he is telling his people to stop supporting falsehood. 

Basically, there is a sense that these people should have known better than to be building and appealing to idols and had simply deviated from the truth. One way this is apparent is that the Qur'an does not explain everything anew; rather, there is an assumption in the text that the people hearing about the stories of the prophets are famliar with them and it is all part of a common cultural and religious context, even if some people were appealing to idols.

The Ka'bah, in particular, is seen as originally being a site of worshipping God, built (or re-built) by Ibrahim (A), but the practice in it became corrupted (for instance, through people performing the hajj in the nude, or placing false idols in it). So the job of these prophets is to remind the people of how they have gone wrong, and then to provide some new religious legislation and teachings (such as the shari'ah and Qur'an) to steer the boat in the correct direction in the future. 

This is rather different from, say, someone who grows up as a secular agnostic, has no real contact with organized religion, and then converts to Islam as a new faith.

So this is how the matter is understood in Islamic sources. 

In any case, that was then and these were prophets; today, there is no need to go around breaking people's idols. Also, most modern idols are invisible things, such as money, celebrity status, number of likes on Facebook, and so forth which cannot be broken even if one tried. 

In any case, it is a good question and good to think about.