Rav Soloveitchik explains the conversion process of a gentile (Kol Dodi Dofek, Conversion by Circumcision and Immersion 2):
A gentile who wishes to join the nation must take upon himself both covenants. He places himself in the ambit of Jewish fate and sanctifies himself for the acceptance of the Jewish destiny. The act of conversion involves associating oneself as a member of the people of the Covenants of Egypt and of Sinai. Keep this important principle in mind: there is no such thing as partial conversion. One cannot omit one iota of either of these two Covenants. Total devotion to the Jewish people — as a nation that God took to Himself in Egypt, with all its tribulations, suffering, responsibilities, and actions; and as a holy people that is itself consecrated, heart and soul, to the God of Israel and His halakhic and moral demands — is the absolute foundation of Judaism and hence is also the basis of conversion. (emphasis mine).
Rav Soloveitchik thus explains that associating oneself as a member of the people of the Covenants of Egypt and of Sinai is a way to connect oneself to the Jewish people.
According to the Or HaChaim on Leviticus 19:34, these converts where people whose soul were already attached to that of those from the Jewish people.
[...] This is why the Torah describes them as "like one of your very own," i.e. you have much more in common with converts than you think. [...]
The only reason these proselytes are embraced wholeheartedly by the Torah is that the Torah views these converts as people who are returning to their roots.
So, according to this opinion, the converts were not really that "strangers", they were already somehow attached to the Jewish people, and found out of their spiritual connection to them.
There are also sources that discuss the fact that after Yisro went to visit Moshe Rabbeinu in the desert, he went home to convert his people. Rashi, in his commentary to Shemos 18:5 explains that Yisro came to the desert "to hear the words of Torah". So, according to this, it would seem logical (did not have seen any sources for this though), that Yisro spoke these words of Torah, he just learned, to his people in Midian, to where he returned. It would seem logical that there were people that would feel an connection after hearing these words of Torah, and wanted to convert. (see here).