Disclaimer: I am not a parent, but I grew up in a very homogenous environment - small US Midwestern town, ~97% white, everyone I knew went to some form of Protestant church.
What helped me was learning about other cultures and worldviews and developing a sense of empathy. Critical thinking skills are essential too - they go hand in hand with keeping an open mind - but you must have empathy first. I know too many arrogant atheists who will play devil's advocate for racists, but can't imagine why anyone would possibly be deluded into religious beliefs.
For example, my parents provided a fairly detailed religious curriculum. Even though I was raised in a particular religion, and the curriculum was definitely biased for that, the studies went into detail and challenged me to think in terms of other worldviews. One course discussed "what are the questions a religion tries to answer?", and we went through how our religion answered them, and then how other religions answer them. It helped me imagine what it would be like to see the world through the other religion's lens.
Encourage them to read. Books encourage one's imagination, and they place you in the shoes of people in diverse situations. Your kids might not know anyone who is gay, but reading an age-appropriate novel with a gay protagonist helps them picture what a gay person might experience.
Another resource is the internet. (Again, sticking to age-appropriate sites.) I was part of a forum with kids having similar interests as me, and we got into some discussions about political and social issues. These kids were mostly not of the same background as me, so I was exposed to more ideas, and they prompted me to defend my beliefs and vice versa. Again, developing critical thinking skills and learning to see things from multiple angles. They may even develop friendships or pen-pal relationships and learn about everyday life for someone having a radically different lifestyle than theirs!
I also want to point out that travel is not a magic bullet. That includes missionary or volunteer travel. That's not to say it never helps, but it could do nothing just as well! For instance, someone who volunteers abroad may come away saying "Oh, those poor natives, what a pity they don't have the comforts of my civilized society", still thinking they are better than them. Or you could take a vacation to a foreign country and say "I can't believe there was graffiti on that wall, such disrespectful and disgusting people". You seem to have observed this already with some of the students studying abroad, but it's worth pointing out.