As each of the religions developed into sects, the primary focus in this article is that of Christianity.
France had , throughout the Reformation and beyond, been the vanguard of Roman Catholicism in Europe and had generally seen itself as the protector of Catholic pilgrims to Jerusalem.
In Russia, the princes of Moscovy saw themselves as the heir to the Byzantine Empire when Constantinople fell in 1453. This led to the adoption of the Byzantine double-headed eagle as well as the title 'Caesar' - Tsar .
Throughout Russia's history with the Islamic khanates and Ottomans in the Crimea, the leading Tsars promoted the Russian Empire as a 'Sacred Orthodox crusade '. 
Russia had a de facto obsession with Jerusalem; the iconic onion-shaped domes of Russian churches were seen as an attempt to copy such churches of Jerusalem. (In fact, a mini-Jerusalem was built !)To an average Russian, a pilgrimage to Jerusalem meant salvation.
New methods of travel such as railways and steamships simplified the travel to Jerusalem, particularly the Odessa to Jaffa route  . A French monk had observed that in a typical year, out of 4,000 Christian pilgrims, only 4 were Catholics, with the rest being of the Russian Orthodox Church.
On the 10th of April 1846 (Good Friday), both the Orthodox and Catholic Easters fell on the same day. Amusingly in Jerusalem, both side raced to the Church of the Holy Sepulcher. The Orthodox won the race. The Catholics, behind them, challenged them. A standoff ensued and the monks engaged in a brawl, using everything from crucifixes, candle sticks and lamps to guns.
By the time Ottoman soldiers intervened, 40 people lay dead. Word of the shooting spread, and outrage followed. Perhaps the first episode of the French-Russian rivalry.
|Church of the Holy Sepulcher (note the domes)|
Obviously, that did not work. In fact, Queen Victoria shrewdly commented:
By this time, Russian uniforms (of princes and generals) were a common sight in Jerusalem, as well as the sheepskins and smocks of thousands of peasant pilgrims. The British consul in Jerusalem even warned London that:"Very clever, I don't think him. His mind is an uncivilized one"
"the Russians could, in one night during Easter, arm 10,000 pilgrims within the walls of Jerusalem and seize the city"Meanwhile, the French pursued their own mission to protect the Catholics. By now, it had become evident of the tension around Jerusalem.
On the 31st of October, 1847, the silver star on the marble floor on the Grotto of Bethlehem's Church of the Nativity, was stolen (the star was previously donated by the French in the 18th century). It was widely believed that the Greeks (being orthodox) stole it. The French claimed the right to replace the star and to repair the roof of the Church in Jerusalem; the Russians claimed it was their right and both had cited 18th century treaties.
The sultan, battered by pressure from both sides, decreed in 1852, confirmed the Orthodox paramountcy in the Church with concessions to the Catholics. The French were outraged and (after citing several agreements dating back to Napoleon's invasion, an alliance with Suleiman the Magnificent, the French Crusader Kings of Jerusalem and even to Charlemange! ), the Sultan granted paramountcy to the Catholics.
Nicholas was deeply outraged at this act and demanded the restoration of Orthodox rights in Jerusalem as well as an 'alliance' that would've effectively reduced the Ottoman Empire to a Russian protectorate!
When the Sultan refused, Nicholas invaded Ottoman territories in Romania and believing that he had Britain's approval in it. He was gravely mistaken.
Britain and France threatened war, Nicholas stubbornly refused citing it as a war dedicated to the Christian cause.
On the 28th of March, 1853, the French and British declared war on Russia.
The great Franco-Russo rivalry finally manifested into the Crimean War.
1. Simon Sebag Montefiore's Jerusalem: A Biography (page 339)
2. Montefiore (page 339)
3. Montefiore (page 340)
4. W. Bruce Lincoln's Nicholas I (page 223)
5. Montefiore (page 340)