Ultimately this story comes from the biography of Saladin by Baha ad-Din ibn Shaddad. Richard was often sick with malaria, and near the end of the crusade in 1192:

“…there was a steady stream of emissaries from the king of England requesting fruit and ice. In his illness God had burdened him with a yearning for pears and plums, which the sultan was supplying him with, while purposing to gain intelligence by the to-and-froing of the messengers.” (Baha ad-Din, 227-228)

Not lemons, but most of the biographies of Richard and Saladin mention this story in one way or another. On other occasions Saladin sent Richard “fruit and ice” (or Richard’s ambassadors ask for that, specifically).

In the years before the Third Crusade, when the Frankish kingdom in Jerusalem was still intact, Saladin had a fairly good relationship with the crusader kings. They were enemies, of course, and they frequently fought and made peace, but there seems to have been a bit of mutual respect on both sides.

They first encountered each other in the 1160s when King Amalric invaded Egypt; after a complicated series of events, Saladin ended overthrowing the Fatimid rulers of Egypt and installing himself as sultan. Saladin later inherited most of Syria as well, so crusader Jerusalem was surrounded by Saladin’s domains.

When Amalric died in 1174, he was succeeded by his son Baldwin IV. Saladin sent Baldwin a letter expressing his condolences:

“the master of a house cannot but be saddened by the loss of his neighbours... The king must know that we have a sincere affection for him, as we had for his father... Let him rely on us.” (Lyons and Jackson, pg. 75, quoting the medieval author al-Qalqashandi)

But otherwise there isn’t really much evidence that Saladin and Baldwin communicated, directly or indirectly, and we don’t really know what Saladin thought of him. Everyone knew Baldwin had leprosy, and the common belief on the Muslim side was that he wasn’t really in charge:

“It chanced that Amaury, king of the Franks (God curse him) had died at the beginning of this year. He was one of the bravest of their kings, the most outstanding for policy, cunning and intrigue. At his death he left a leper son, who was incapable of ruling. The Franks made him king in name with no substance to his position. The conduct of affairs was undertaken by Count Raymond with power of loosing and binding, whose command all followed.” (Ibn al-Athir, vol. 2, pg. 234)

They felt that Raymond III of Tripoli and Baldwin’s other advisors were the real authorities, the ones that Saladin negotiated truces with. From the Frankish point of view, that was true sometimes. Baldwin was often incapacitated from his disease, so Raymond (or other people like Guy of Lusignan or Raynald of Chatillon) acted in his place, but sometimes Baldwin was healthy enough to lead the army in person. The most notable example is probably the Battle of Montgisard in 1177, where Baldwin defeated Saladin, despite still being a teenager at the time. He was only 16 and certainly some of the credit should go to Raymond, but Baldwin’s presence at the battle was apparently a big boost for the Franks.

In 1183 Saladin attempted to besiege the fortress of Kerak. There was a wedding taking place there at the time, between Baldwin’s stepsister Isabella and Humphrey IV of Toron. According to a Frankish legend, Saladin had once stayed at Kerak as a child, and was still friendly with Humphrey’s mother, who sent Saladin’s army some of the wedding feast; in response Saladin agreed not to attack the castle’s chapel. Whatever really happened, Saladin was forced to retreat when Baldwin came to relieve the siege. This time though Baldwin’s presence was mostly symbolic, as he could no longer walk and had to be carried in a litter. Raymond of Tripoli was really in charge.

Baldwin wasn’t always victorious; in 1179 Saladin defeated the Franks at the battles of Marj Ayyun and Jacob’s Ford. But usually, the arrival of a Frankish army (whether led by Baldwin or not) was enough to force Saladin to withdraw, so it’s assumed that Saladin respected the strength of his army, at least.

At the time though, in the 1170s and early 1180s, Saladin wasn’t fully in control of his Syrian possessions. To the north in Mesopotamia, he often had to intervene and put down rebellions, so it was a drain on his forces to fight rebellious lords in the north and the Franks in the south. What seems to be Baldwin’s strength, from the Frankish perspective, was probably often Saladin’s recognition that he couldn’t fight on two fronts at the same time. He would have to consolidate his control over Mesopotamia before he could fully invade the Kingdom of Jerusalem. The Franks were apparently mostly unaware of this. Things fell apart when Baldwin died in 1185, and Saladin was able to invade and almost totally destroy the kingdom in 1186-87.

Unfortunately, as far as I can see, Saladin never shared what he thought about Baldwin personally, or at least no one recorded what he thought, if he thought anything.

When Richard arrived on the Third Crusade in 1191, Saladin was in control of almost the entire land, so his situation was much stronger than it had been ten or fifteen years earlier. Where Baldwin was ruling in his own country with all of its resources at his disposal, the new crusaders had to re-establish a foothold and then fight and supply themselves in a foreign territory that they only barely controlled.

More people around Saladin were writing about the crusade, so it’s a little bit easier to see what he thought of Richard. But in fact Saladin wasn’t quite sure what to make of the English king, who acted like he was an equal, as if he had a much stronger position than he really had.

Richard sent ambassadors to Saladin as soon as he arrived and asked to meet with him in person, but Saladin couldn’t agree. He was concerned that two kings meeting in person might hastily agree to things that couldn’t work in reality, and then it would be awkward to fight a war against each other. Besides, they didn’t speak the same language, and Saladin felt it was inappropriate to communicate with another king through an interpreter.

But they did communicate indirectly through ambassadors and interpreters. Sometimes Richard also met with Saladin’s brother al-Adil (known in crusader sources as “Saphadin”), which seems to be a pretty high honour. Nevertheless al-Adil and Saladin considered him a bit untrustworthy and treacherous. They assumed that whenever Richard offered to make peace, it was only so he could gather his forces and attack again later.

There is a famous story that Richard suggested al-Adil should marry his sister Joan, and the two could rule a joint Christian-Muslim kingdom in Jerusalem. The story is only found in the Muslim sources though, so we’re not entirely sure what happened from the crusader viewpoint. Saladin obviously couldn’t quite believe these plans himself, but called Richard's bluff,

“believing that the king of England would not agree to them at all and that it was intended to mock and deceive him.” (Baha ad-Din, pg. 188)

Sometimes Saladin was annoyed that Richard was asking far more than it was possible to give. Richard wanted Jerusalem back, even though he couldn’t take it by force, and Saladin couldn’t and wouldn’t simply give it back. During the Siege of Acre in 1191, Richard massacred about 3000 Muslim prisoners, possibly because he just couldn’t afford to feed an extra 3000 people, or possibly in retaliation for Christians who had been killed during the siege (although those soldiers had died in the course of regular fighting). Either way, Saladin was furious, and he felt he had no choice but to execute his own Christian prisoners.

I’ve mentioned in a previous answer that their supposedly friendly and respectful relationship is more an invention of modern romance, probably originating with the novels of Walter Scott. In reality they didn’t exactly trust each other and Saladin always assumed Richard had treacherous motives.