In The Left Hand of Darkness there is a planet where the natives are usually androgynous, but go through cycles of “estrus” where they become temporarily male or female, for breeding purposes mostly. Some individuals virtually always became either male or female, but others might be male at one cycle and female at another, depending on circumstances.
The protagonist in Maureen McHugh’s Mission Child starts as a woman who decides to pretend she’s a man for safety reasons. (There’s a funny scene when a friend tries to teach her to act like a man. He starts with offering her a bowl of peanuts, and when she takes a single one and eats it he tells her she should have grabbed a handful. 
) Her/his view of her/his own gender changes during the book, and near the end of the book, when asked “Are you a man or a woman?” answers “I’m Janna.”
The comic series The Invisibles features Lord Fanny, a mtf transexual as one of the main characters, although she is already living as a female a the start of the comic.
Alan Moore’s Promethea is about a girl who becomes the incarnation of an ancient Goddess who has had several different incarnations through history. One of her previous “hosts” was a gay man, who transformed into the female Promethea to fight evil. The same comic has a minor character who used to be a male superhero, but was transformed into a woman through some unexplained (at least, unexplained at the point I am in the series) circumstance into a woman.
Camelot 3000 was a sci-fi retelling of King Arthur, in which Sir Tristan is dismayed to find out he has been reincarnated as a woman. Isolde doesn’t seem to mind, though.
Grant Morrison’s run on Doom Patrol featured a character that was created as a melding between a man, a woman, and an extra-terrestrial energy-based life form.
The movie Escape from L.A. had Pam Greer playing a mtf transexual car thief.
Lois Bujold’s space opera series, Barrayar, features a planet with highly advanced biological sciences that make gender swapping relatively easy, and is home to a race of genetically engineered hermaphrodites. In A Civil Campaign. a Barrayaran noblewoman travels there to change her gender, to circumvent Barrayar’s patriarchal inheritance laws. (The series includes a book, Ethan of Athos, about a planet inhabited solely by gay men.)
In yet another Heinlein instance, in the later meta-universe novels (yeah, I’d like to deny their existance), Andrew Jackson Libby was brought back to life as a woman, re-named “Elizabeth”.
And this probably doesn’t count, since e didn’t really have a true “gender” at all, but Mycroft Holmes from The Moon is a Harsh Mistress takes on a male personna (“Mike”) when talking with Manny, but a femal personna (“Michelle”) when talking with Wyoh. Wyoh insists that e’s truly female, though, based on es taste in jokes.
Oh, and back on the folklore, popular wisdom centuries ago had it that succubi and incubi were the same beings in different forms. The only way an incubus could impregnate a woman was with stored sperm collected in succubus form.
I have the first two volumns of that!
Also, wasn’t there a Supervillian that had the apperence of a steretypical superhero?
Ah, yes, it was Captain Power, also known as Dr. Christina Carr.
Come to think of it, the same page I am lining from has a whole list. Bottom of the page.
That was who I first thought of when I saw the OP: Ranma changes gender hundreds of times in the course of the manga and anime series, just as his father changes between human being and panda. And there’s the running joke in the series that a lot of people think that Ranma-kun (boy) and Ranma-chan (girl) are two different people, and may be in love with one of them and want to kill the other.
I think you’re misrecollecting here. No one is “re-incarnated” in Camelot 3000 and no one changes sex, as far as I can recall. It doesn’t fit the OP’s description.
The Japanese animation Rei Rei, about Kaguya the moon goddess, features a character who temporarily changes gender.
No, I am pretty sure that Miller has it right.
Let’s see…
Lord Dono/Lady Donna from A Civil Campaign, Lois McMaster Bujold.
The wizard Elminister from the Forgetten Realms D&D setting spent years as a woman, as a disguise.
The Anarae from David Eddings Tamuli books mentioned she could become a man; she found it “untidy”.
Belgarath the Sorcerer ( also from Eddings ) once accidentally changed into a female owl.
Lastel Longknife got cursed with a womans form in Mercedes Lackey’s Oathbound.
In one of Alan Dean Foster’s Spellsinger books, the entire group of adventurers switches sex for a small time.
Baron Mordo ( one of Dr Strange’s enemies ) possessed the body of a woman named Morganna.
In Brother Death by Steve Perry, there’s a MTF transsexual by the name of Pickle; she named herself after the ex-body part she keeps in a jar.
Another mention for Jack Chalker; sex changing and transformation are common in his stories.
In War Games and Dream Games by Karl Hansen there is multiple gender switching, including shapechangers ( Chameleons ), a boy turned into a catwoman, and another into a child hermaphrodite.
From Sorcerer’s Son by Phyllis Eisenstein, one of the characters is a demon named Gildrum; he/she has both male and female bodies.
I entered this thread to mention Jack Chalker. The previous post mentioned that Chalker likes sex changes a lot. In point of fact, in every Chalker book I’ve read, everybody changes gender and species many times. He’s obssessed with it. A male Human may become a female Arcturan. The characters never have any choices in what they become. I’ve often thought that a psychological deconstruction of Chalker’s books might make better reading than the books themselves.
The people from Iain Banks’ Culture books can change gender any time they feel like it.
In a Star Trek novel, Q appeared as a stunningly beautiful woman for a short time; he said something like “Picard, maybe you’d like me better if I had first appeared to you like this”
In the old ( bad ) movie The Sword and the Sorcerer, the evil sorcerer changes one of his henchmen into a duplicate of the hero’s girlfriend.
Actually, he’s commented that one of the reasons he does that is his fans keep writing him about how much they like it.
Nope, Miller’s correct, and you’re misremembering.
From Camelot 3000’s Who’s Who entry (1985 series, issue 3):
Maybe we’re talking about two differnt Camelot 3000s? The one I’m thinking of was a DC comic published in the '80s, wherein an alien invasion of Earth leads to the re-awakening of King Arthur from his tomb in Glastonbury Tor. The rest of the knights have all been re-incarnated as modern day people around the globe, with no memories of their past lives. Merlin uses little sword-shaped pendants to bring their old selves back to the surface. Tristan has been reincarnated as a woman, and has his memories reactivated in the middle of her wedding. It’s very much in keeping with the OP, as Tristan’s gender conflict is one of the central facets of his character (he identifies very strongly as male, once he remembers who he was), and is used by Morgan le Fey as a lever to get him to betray the Round Table.
Oddly, despite being 1000 years in the future, and having access to billions and billions of dollars (Lancelot has been re-incarnated as a very wealthy man. Wealthy as in own-your-own-asteroid-fortress wealthy.) nobody ever thinks to suggest he look in gender reassignment surgery, or even some hormone treatments.
Marion Zimmer Bradley’s Lythande is about a woman posing as a man until the end of the world (rather complicated).
The Beacon at Alexandria by Gillian Bradshaw is about a woman in ancient Greece who poses as a man to become a doctor in Alexandria.
I remember a short story set in a world were reincarnation is a known fact; the government is seeking to capture and suppress the existence of the reincarnation of Jesus Christ; “The bad news is, she’s black”.
I have a 1960s pulp adventure novel called The Death of the Fuhrer where the same thing is done with Hitler’s brain.
Turnabout Intruder actually.
The Starlights from anime version of SailorStars is rather ambiguous in gender. IIRC, they’re women (or genderless), and then they take the bodies of (rather androgynous) men, and change again into women when they transform.
I also seem to remember that Naoko Takeuchi (Sailor Moon’s mangaka) was not entirely happy about this change, since she wanted it so that only women could be Sailorsenshi.
Myra Brekenridge( by Gore Vidal) changes to Myron.“Where are my breasts? Where are my breasts?”
And then back into Myra for the sequel, Myron.
Starhawk of Marvel’s Guardians of the Galaxy is another of the “merged lovers” type of sex change.