An interesting one, which can be linked to some of my own Byzantine 'what ifs' in its origins - a weaker Moslem military and overlordship presence in the Caucasus over centuries would logically have resulted in less of a motive to convert as there would be less of an appeal for linking up to the regional overlord's religion (for civilian and military jobs, security from raiding as 'infidels', less taxes etc). The two main regional overlords until the Russians arrived on the scene - first in the 1690s to 1720s by Peter the Great, who retook Azov at the head of its Sea from the Ottomans only to lose it in 1711 in a messed-up campaign in Bessarabia/ Moldova , and then permanently under Catherine II, Paul, and Alexander I - were both Moslem, ie the rival Ottomans (Sunni) and Iran (Shi'a). They both used the main (southern) Caucasus Christian kingdoms in Georgia , divided from the 1460s and by the 1500s substantially weakened by constant war and internal feuds, as a source of loot , tribute and slaves via raiding from the early 1500s, made the Georgian monarchs their vassals when they were strong enough, and from time to time subdued them totally or imposed/ used a monarch who had converted to Islam as their local puppet - giving incentives to his elite to convert too. (Quite a number of Georgian nobles ended up at the Iranian court as courtiers/ officers under the Safavids and Shah Abbas, r 1587 - 1629, set up a Georgian quarter at his capital of Isfahan for merchants etc; a lot of Georgian women ended up in the Isfahan elite's harems.)
Without either a very strong Ottoman state interested in/ dominating the southern Caucasus on a regular basis , and without a strong and predatory Safavid state (which had originally been centred in Azerbaijan, with its royal family as local nobles, and so had local links) this domination of the southern Caucasus would be unlikely, and so would conversions to Islam on a long-term basis - and this would not have seeped through into the northern Caucusus beyond the Elbruz range, unless some occasional expeditions by a powerful Anatolian or Iraqi/ Azerbaijani Moslem state had deliberately penetrated the passes and raided the plains beyond to gain prestige and loot and slaves and had sought to convert the local tribes (eg by inviting ambitious warriors to come and serve at their courts and gain wealth provided they converted ) as a Moslem counter-balance to the local Christians (or later Russia). So if we have Anatolia remaining divided in the C15th as a result of Timur wrecking the Ottoman state permanently at the battle of Ankara in 1402, the Ottomans being too weak to defeat the Qaramanids and the White Ram Turks who hold onto the SE and NE of Anatolia, or a failure of the Safavids to take over Iran and Iraq and a weaker local dynasty in Tabriz instead we get a divided and probably non-expansionsist local Moslem power in the Caucasus borderlands and no penetration of Islam beyond the southern Caucasus except by traders and the occasional warlord from the Baku region. The Moslem and predatory but otherwise preoccupied Timur is a temporary occupier and ravager in the 1390s and 1400s as in real life but makes no long-term difference to the region except in him and his heirs demanding tribute and mercenaries, as the Mongols did before him.
Russia can move in quicker and easier , possibly as a result of Peter defeating the Ottomans not the other way round in 1711 and securing the Sea of Azov then plus a supply of local tribesmen for his army as mercenaries, and the tribes of Circassia as Christians are culturally more kin to the Orthodox Russians from staying Christian - or even being converted fully and secured as restive but fearful and usually loyal vassals by a stronger and unified Georgian state in the C15th and C16th. The Russians would still appear as unwelcome intruders and demanders of tribute and troops if the locals had no Ottoman or Iranian threat to make them need Russian help, though - and autonomist rebellions would still be a possibility if the Russians over-reached themselves in excessive demands (eg for help to their armies in taking over the S end of the Caspian Sea, which Peter sought in real life in the 1720s) or their generals were arrogant and predatory. A surviving Georgian state that had not broken up in the mid-C15th and had not been victim to the Ottomans and Safavids (and later the early Qajars) would also face the dilemma of accepting control by its 'Orthodox big brother' in Moscow/ St Petersburg or revolting. Given the plethora of rival local princes, I can see both Circassia and Georgia breaking up into pro and anti Russian factions and a series of complex civil wars - and once the British arrive on the scene (1820s as in OTL?) they would have been supplying arms and commanders as required by London to stir up rebels and keep the Russians from taking over the entire region and then heading on to Constantinople or the Indian borders. The 'Great Game' would have had a Christian Circassian and Georgian theatre, and possibly a Christian version of Imam Shamyl to lead the resistance in the 1840s-50s, but as an autonomist prince resisting Russian 'tyrants' not with a religious dimension. Would the British have tried to convert some restive local leaders to Anglicanism to add to the complications?
