Of course we have:
- Tasha Yar (Denise Crosby)
- Dr. Crusher (Gates McFadden) who left for a season
- Jadzia Dax (Terry Farrell)
- Kes (Jennifer Lien)
(Links are to related questions)
Nichelle Nichols came very close to leaving but was convinced by Martin Luther King Jr to stay, being one of the few recurring black actresses of the time in a positive role.
Her wiki article goes over it, and her autobiography is worth a read.
Nichols' Star Trek character, one of the first African American female characters on American television not portrayed as a servant, was groundbreaking in U.S. society at the time. Civil rights leader Martin Luther King, Jr. personally praised her work on the show and asked her to remain when she considered leaving the series.
According to this article in TrekToday, Michael Dorn (Lt. Worf) nearly left the show after the second season, stating that his makeup was causing damage to his skin:
Dorn said that he was very happy when his makeup time was reduced from two and a half hours to a little over and (sic) hour, confessing that he nearly left the show after the second season because of all the damage to his skin. At one time he did a convention nearly every weekend, but now he does 3–4 a year, "the really cool places" like Italy and Germany. For fun he flies ex-military jets.
This Comic-con interview report states that George Takei (Sulu) nearly left the original series after he was made to share a dressing room with Walter Koenig (Chekov):
When Takei returned, the two had to share a dressing room and a single episode script. This reportedly angered Takei to the point where he nearly left the show. But the two actors have since become good friends, and the image of their two characters manning the helm of the Enterprise became iconic.
According to Star Trek: These Are the Voyages TOS Season 2: Season Two, Leonard Nimoy almost didn't return for season two of TOS due to contractual issues. There are additional details on Memory Alpha:
Nimoy's agent had asked for Nimoy's salary to be increased from US$1,250 per episode during the first season to US$9,000 for the second season. Eventually a compromise figure of US$2,500 per episode was reached and Nimoy signed on for the second season.
According to an interview with Starlog, Kate Mulgrew said that she considered refusing to sign for a seventh season, citing her impatience at being made to wait around all day for pick-up shots in episodes focusing on other members of the cast. Ultimately, the show's producers were able to work things out with her:
...she would be sitting at home for hours, unable to go anywhere or do anything, waiting for production to call her in. And she didn't want too many more instances in which she shot only a single, non-essential scene.
Berman and company heard Mulgrew out, and ultimately they came to an agreement that satisfied everyone. Janeway wouldn't be pulling a vanishing act this year or next. Just how close, though, did we come to losing Mulgrew? "If they had said to me, 'We really don't care,' I may have considered leaving," she responds. "I was under contract already for the sixth year and I intended to honor that contract. I'm only talking about conversations and negotiations for the seventh season. It really involved my happiness quotient. In many ways, I set the tone on the set. My mood and my approach are very important, and I think there's nothing worse than a professional actress who is unhappy because she misses her husband and children. But [Berman and Braga] realized that. And if I may say so, they were not only gentlemen about it, but very gracious. I am much, much happier now."
On the DVD interviews for DS9, Avery Brooks (Commander/Captain Benjamin Sisko) said that he wanted to quit, but at the time had just explained to his son the importance of sticking to your commitments, so he remained.