The most idiomatic way to say “I'm leaving”, appropriate in most contexts, is probably:
Je m'en vais.
It's also common to say “I'm going to leave” rather than “I'm leaving” even if you are already in the process of leaving:
Je vais y aller.
(The last two somehow sound softer than “Je m'en vais”, which could even be slightly hostile, depending on the tone.)
Depending on the exact context,
is also good, perhaps a bit more formal. It would feel most natural in a dialogue like this one:
Pourquoi tu mets ton manteau ?
Je pars !
or for a long journey so that “I'm leaving for Hong Kong tomorrow” would be
Je pars pour Hong Kong demain.
As mentioned by @GAMPUB, it's also possible to signal your intent to leave very soon using “partir” in the past tense.
Je suis parti.
It's a bit surprising on the face of it, since you obviously aren't gone when you say that, but the implication is that you are already late/not available to talk or do something anymore. I would not recommend using it as a language learner, though, it might not always fit the situation.
Similarly, you could sometimes say “I'm not here”/“I'm already gone”:
Je ne suis déjà plus là.
Another odd use of “partir” in this context is
Je me sens partir
which literally means “I feel myself leaving” and can be used in colloquial speech to say that someone wants/intends to leave soon.
Parting with a group
It's also quite common to leave a group by saying
Je vous quitte
Je vous laisse
Je vous dit au revoir
In that case, the emphasis is on the fact that you are leaving the group, not so much that you are leaving a place. In some contexts (say you have to do something or see someone else and won't get a chance to catch up later), you might even say that and stay in the vicinity.
Your third option,
is a bit more difficult to use correctly. Often, there is an implication that you are now in your normal abode and will come back. It's probably not appropriate at an outdoor location.
It's perhaps closer to the English “I'm going out”, including when talking about a night out so that “I'm going out tonight, I have been invited to the restaurant” would be:
Je sors ce soir, on m'a invité au restaurant.
And, together with “avec”, it implies a sexual/romantic relationship but not a deep love/long-term relationship (a bit like “to date”, although not quite, as I think “sortir” means you have a relationship, not that you are merely flirting/hoping for one as “dating” sometimes imply in English):
Elle sort avec Nicolas.
“Sortir” is also what you would use when speaking about leaving a vehicle, but not necessarily with the intent of parting with your company:
Je sors de la voiture, tu viens ?
Beyond that, there are literally dozens of other ways to say “I'm leaving” in slang
Je me sauve
Je me casse
Je me barre
Je me tire
Je fous le camp
Je fiche le camp
Je plie bagages
Je prends la tangente
Je trace [la route]
Je [me] taille
Je cargue la voile
Je vide les lieux
Je me translate
Je largue les amarres
Je lève l'ancre/le camp
Je me fais la malle
Je mets les bouts/les cannes/les bois/les bâtons
Je mets les adjas
Je prends la fille de l'air [sounds a bit odd with the first person actually]
Some of these (e.g. “Je file”) are only slightly colloquial and could be used in many contexts but many are obscure, very informal or have other connotations and should not be used without knowing exactly what you are doing.
is not grammatically incorrect but it means literally “I go”, not “I'm leaving”. I can't think of a context in which you could use it alone without sounding overly formal, in standard spoken French it's only common to introduce an action that will happen in the immediate future (a bit like “I'm going to” in English):
Je vais marcher
Je vais aux toilettes
Je vais y aller
Je vais me faire mal si je continue