The gospel has always been a challenge, not only because it humbles the powerful by "casting down the mighty in their arrogance" but also because it welcomes the outsider and affirms whatever can be affirmed in common with him in the hope that grace will be able to build on that and bring those in partial union to full union.

Case in point:

John answered, “Master, we saw a man casting out demons in your name, and we forbade him, because he does not follow with us.” But Jesus said to him, “Do not forbid him; for he that is not against you is for you.” (Lk 9:49–50).

John had definite ideas of who was in and out. Jesus blew them to pieces by pointing out that just because somebody was not one of us did not mean his grace could not reach them and work through them.  Notice that Jesus doesn't say "Everybody can therefore feel free to blow off the Church".  Rather he says that those in visible communion the Church must not feel free to blow off those who are not.  In short, he calls us to keep our eyes peeled for those occasions on which he has gone ahead of the Church and planted his semina verbi--seeds of the Word--in the hearts, minds and cultures of human beings who are made by God to seek him.

Paul got the message.  That's why he did not ream out the Athenians for being pagans but instead appealed to their own poets and their own religious heritage to point them to Jesus:

Now while Paul was waiting for them at Athens, his spirit was provoked within him as he saw that the city was full of idols. So he argued in the synagogue with the Jews and the devout persons, and in the market place every day with those who chanced to be there. Some also of the Epicurean and Stoic philosophers met him. And some said, “What would this babbler say?” Others said, “He seems to be a preacher of foreign divinities”—because he preached Jesus and the resurrection. And they took hold of him and brought him to the Are-opagus, saying, “May we know what this new teaching is which you present? For you bring some strange things to our ears; we wish to know therefore what these things mean.” Now all the Athenians and the foreigners who lived there spent their time in nothing except telling or hearing something new.
So Paul, standing in the middle of the Areopagus, said: “Men of Athens, I perceive that in every way you are very religious. For as I passed along, and observed the objects of your worship, I found also an altar with this inscription, ‘To an unknown god.’ What therefore you worship as unknown, this I proclaim to you. ¶ The God who made the world and everything in it, being Lord of heaven and earth, does not live in shrines made by man, nor is he served by human hands, as though he needed anything, since he himself gives to all men life and breath and everything. And he made from one every nation of men to live on all the face of the earth, having determined allotted periods and the boundaries of their habitation, that they should seek God, in the hope that they might feel after him and find him. Yet he is not far from each one of us, ¶ for
    ‘In him we live and move and have our being’;
as even some of your poets have said,
    ‘For we are indeed his offspring.’
Being then God’s offspring, we ought not to think that the Deity is like gold, or silver, or stone, a representation by the art and imagination of man. The times of ignorance God overlooked, but now he commands all men everywhere to repent, ¶ because he has fixed a day on which he will judge the world in righteousness by a man whom he has appointed, and of this he has given assurance to all men by raising him from the dead.”(Ac 17:16–31). 

And so the Church has done ever since, affirming what can be affirmed in common while never pretending "We're all saying the same thing" where we, in fact, disagree.  So, for instance, here is Pope St. Gregory VII (†1085) writing to the (Muslim) King of Mauritania:

"[F]or Almighty God, Who desires that all men shall be saved and that none shall perish, approves nothing more highly in us than this: that a man love his fellow man next to his God and do nothing to him which he would not that others should do to himself.

This affection we and you owe to each other in a more peculiar way than to people of other races because we worship and confess the same God though in diverse forms and daily praise and adore Him as the creator and ruler of this world. For, in the words of the Apostle, 'He is our peace who hath made both one.'

This grace granted to you by God is admired and praised by many of the Roman nobility who have learned from us of your benevolence and high qualities.[. . .]

For God knows our true regard for you to his glory and how truly we desire your prosperity and honor, both in this life and in the life to come, and how earnestly we pray both with our lips and with our heart that God Himself, after the long journey of this life, may lead you into the bosom of the most holy patriarch Abraham." 

Is that indifferentist modernist post-Vatican II glop?  Nope.  It's a sainted pope affirming what can be affirmed in common with a Muslim.

In Apollo 13, Gene Kranz, the guy in charge of the flight at Mission Control, is confronted with the problem of saving the crew of the crippled ship and bringing them safely home after an explosion in the command module seems certain to doom them.  As his first step in analyzing the situation, he makes a deeply Catholic choice.  He asks not, "What is broken on the spacecraft?" but rather "What do have on the ship that's good?"

Nostra Aetate takes the same course, as does Unitatis Redintegratio.  The Church surveys the various religious and philosophical traditions of the world, as well as the various forms of Christianity beyond the Catholic communion and asks first not, "Where are they wrong?" but "Where are they right?"  This is not a pollyanna question which denies our differences.  It's a Thomistic approach which insists that grace builds on nature and seeks to find whatever chunks of natural goodness that can be found in other religious and philosophical traditions out there, just as Paul did.  It is also a recognition that the Light which lightens every person is free to do his work outside the visible Church as he did with the exorcist John was fretting about.  And it is, finally, the recognition that we really do believe in one baptism for the forgiveness of sins, so other baptized believers beyond the visible Church are therefore in a real, albeit partial, union with the Church.

Are we "all saying the same thing"?  Of course not.  But neither is it true that we have nothing whatsoever in common.  We are all made in the image and likeness of God.  Therefore, Catholics and pagans have that, as well as the natural law, in common in various ways.  In the case of Abrahamic religions (Christianity, Judaism, and Islam) we have even more in common professing the God of Abraham and, for instance, performing such practices as prayer, fasting and almgiving.  And in the case of other Christian traditions, we have even more in common in various ways.  As C.S. Lewis puts it:

If you are a Christian you do not have to believe that all the other religions are simply wrong all through. If you are an atheist you do have to believe that the main point in all the religions of the whole world is simply one huge mistake. If you are a Christian, you are free to think that all those religions, even the queerest ones, contain at least some hint of the truth. When I was an atheist I had to try to persuade myself that most of the human race have always been wrong about the question that mattered to them most; when I became a Christian I was able to take a more liberal view. But, of course, being a Christian does mean thinking that where Christianity differs from other religions, Christianity is right and they are wrong. As in arithmetic—there is only one right answer to a sum, and all other answers are wrong; but some of the wrong answers are much nearer being right than others.

This is a deeply Catholic view of things and makes it possible for Catholics to have a conversation (the technical term is "dialogue") with somebody like Lewis (an Anglican) and with the Anglican communion about why there is a reasonable case to be made, not only for the things we hold in common, but for those things the Catholic communion affirm and Anglicanism denies. And the same applies to other religious traditions too.

Some Catholics flinch at this and think that "dialogue" is a weak tea word for evading our responsibility to evangelize.  But when pressed on this, it often appears that "evangelism" means, for such folk, grabbing people by the lapels and demanding they turn or burn.  This is not what Jesus or the apostles did and it is not what people with elementary social skills do either.  Rare is the man who succeeds in wooing a woman with "I love you!  Marry me or I will destroy you!"

To be sure, Jesus warns of eternal consquences if we refuse the offer of life.  But that is because he is talking to people who have seen just how attractive and beautiful the life he offers is and who are fighting it out a perverse love of money, power, pleasure, and/or honor.  Like Scrooge offered the chance to marry his sweetheart and be truly happy or cling to money and throw it all away, Jesus warns those who have had a good look at the happiness he offers that if they reject happiness they will indeed find only unhappiness through all eternity since happiness is Him.

So Jesus and the apostles tend to start with where we are.  They trust that God the Redeemer is also God the Creator and the good things he puts in our hearts, such as the natural law, love of beauty, love of family and so forth will lead back to him since they come from him--just so long as we don't make idols of them and try to pretend they themselves are God.  Jesus and the apostles also trust--and teach the Church to trust--that we can therefore forge common bands of humanity with others even if they are not Christian.  Again, that does not mean "we're all saying the same thing".  We're not sometimes.  But many times we are.  This forms the basis for things like this:

It's not a claim that all religions are salvific. It's a call to obey the second greatest commandment "Love your neighbor as yourself" and say "If possible, so far as it depends upon you, live peaceably with all" (Ro 12:18).  The faith trusts that in doing so, every human person is, whether they realize it or not, acting in obedience to God. And Jesus tells us that "whoever does the will of my Father in heaven is my brother, and sister, and mother." (Mt 12:50).

"But they have not been baptized!"  True.  And if the pope was saying they are Christians and had been born again in baptism, that would really matter.  But he is not.  What he is obviously doing is saying they share in our common humanity and in the natural law, just as Paul said to the Athenians as he sought to affirm what could be affirmed in common with non-Christians.  He is pointing out that the Spirit blows where he wills as Jesus pointed out to John when he tried to stop somebody from doing the will of Jesus because he didn't have the right Club Membership card.  He is calling all to work for the common good.

The pope is pointing the way to a different kind of confidence in Jesus Christ: a confidence which believes that because He is the Creator of all, therefore when anybody responds to the natural law Jesus has placed in their heart and loves his neighbor, he is moving toward salvation in Jesus by obeying Jesus.  This is, in fact, the lesson of the Parable of the Sheep and Goats.  Recall that the Sheep, as well as the Goats, have no idea that it was Jesus they served (and rejected) as they loved (or refused to love) their neighbor.  So the Church, like Jesus and the apostles, begins its work of evangelization with people wherever they are, confident that in following the natural law and the law of love, it will lead to Jesus.

Does this mean we should not invite people to become Catholic?  Certainly not!  As opportunity affords we should always be inviting people to seek Jesus Christ, fully present in the Eucharist. If Jesus is working in the lives of those who do not yet know him, how can we not desire that they know him in full?  But we have to realize that the way Jesus shows himself is from the inside out.  Peter was not converted by Jesus grabbing his lapels and telling him "Turn or burn!"  He was converted when he freely confessed--because the beauty of Christ compelled him to do so--that "You are the Christ, the son of the living God."  When we call people to love, whatever their religious background, we are calling them to Christ who is Love.  If they pursue love to the end, they will find him.