Origin: Ben stumbled upon Richard while searching for his mother's ghost.
Since Then: Richard didn't let Ben into the Others at first, urging him to be patient. A few years later, Richard healed him in the Temple. Ben worked with the Others while living with the DHARMA Initiative, and Ben and Richard together carried out the Purge. Ben became the Others' leader, and Richard brought him instructions from Jacob, including several lists. Richard also occasionally left the island for such errands as recruiting Juliet. After the survivors kidnapped Ben and attackers arrived from the freighter, Richard brought a group of Others to rescue him. Ben then left the island for a few years, then returned and inadvertently helped the Man in Black kill Jacob. Richard and Ben worked together for some days to keep the Man in Black on the island.
Origin: Eli was one of several people in Richard's group of Others
Since Then: Eli was in the Others' hierarchy till she became the latest of several leaders who Richard advised. When a strange man entered the camp and put a gun to Richard, she shot him to save her adviser. The two worked together to retrieve the nuclear bomb they'd once buried, and Richard knocked her out, allegedly to protect her. She left the island soon after, and they may have met again during Richard's frequent off-island trips.
Origin: Richard tried to kill Jacob, thinking him the devil.
Since Then: Jacob convinced Richard that he was not the devil, and the island was not hell. He explained its purpose and hired Richard and an intermediary between himself and the people of the island. Richard served this role for almost 150 years. Jacob withheld a lot of information from Richard during this time, including any information about his candidates, and when Jacob died, Richard lost all faith in him.
Origin: A time traveling Locke approached Richard, claiming to be his leader
Since Then: Richard visited Locke three times off-island but failed to see anything special about him. When Locke crashed on the island though, Richard learned the paralyzed man could now Locke. Ben demanded Locke kill his father to join the Others, and Richard helped him get Sawyer to kill him instead. When Locke became the Others' leader, Richard welcomed him. The Man in Black later approached him in Locke's form, surprising Richard with his new-found purpose. At his instruction, Richard approached another time-traveling Locke with directions and a compass.
Origin: The Man in Black recruited Richard as soon as he landed on the island to kill Jacob.
Since Then: Richard chose instead to work for Jacob, and he announced his decision to the Man in Black. Years later, after taking Locke's form, the Man knocked Richard out and again asked him to join him. Richard refused and began advising candidates to refuse him too. When his suicide attempts failed, Richard gave up and called to the Man in Black, asking to join him after all. He didn't end up joining him though and instead sought to destroy his means of escaping the island.
Origin: Sawyer approached Richard in 1974 and convinced him he was a time traveler.
Since Then: Sawyer became DHARMA's head of security, and he and Richard presumably met periodically over the next years. By 1977, they were on first name basis. Sawyer approached Richard with Ben Linus's body, and Richard agreed to heal him. Decades later, when Oceanic 815 crashed on the island, Richard helped prepare James's file and noted his search for the original Sawyer. He then handed this file to Locke, letting Sawyer kill Cooper. A few years later, after Jacob died, Richard approached Sawyer and frantically warned him against the Man in Black. The two escaped the island on a plane shortly after.