Babel-17
by Samuel R Delany (1966)

Delany boldly went where no man had gone before by giving Babel-17's female hero characteristics normally reserved for macho-males. The Earth Alliance is receiving alien language (Babel-17) communications which apparently threaten invasion. The hero captains a spaceship across the galaxy to try and crack the code. Ripping space operatic fare.

The Left Hand of Darkness
by Ursula K Le Guin (1969)

Intellectual sci-fi classic that still rouses lively debate. A 'normal' human emissary travels to the wayward world called Winter, where the hermaphroditic inhabitants are real live gender-benders. Along the way he forgets his training, gets involved in local politics, and has to face up to his sexual prejudices. Indispensable reading.

The Female Man
by Joanna Russ (1975)

Four versions of the same woman exist simultaneously in radically different realities - a utopia, a near-future dominated by gender conflict, an alternative timeline and the 'contemporary' 70s. They meet and, as a result, feminism makes furiously funny and subversive inroads into our hearts and minds. Famous feminist classic.

Woman on the Edge of Time
by Marge Piercy (1976)

Thirty-something Connie Ramos is wrongly declared insane and sent to NYC's Bellevue Hospital. Her telepathic abilities give her access to a gender-bending future utopia choc-full of role reversals. Social harmony, however, doesn't change the fact that there is no place like home. You just have to be willing to fight for what's right.

Dreamsnake
by Vonda N McIntyre (1978)

Explorations of gender abound in this story of a post-apocalyptic healer who uses medicinal snakes to treat her patients. Her prized alien dreamsnake gets killed and she sets off to look for another one. Le Guin notes that, "Merideth is the first non-gendered non-alien character I ever met in fiction." Most of us didn't seem to notice.

Friday
by Robert A Heinlein (1982)

Although Heinlein was far from the peak of his powers with this later effort, it is still an enjoyable romp that contains an occasional insight of note. Friday Jones is an AP or 'Artificial Person' struggling for acceptance in a near-future where she works as a secret courier. Heinlein's Libertarian ideals are again evident and, of course, as with many of his later works there is plenty of sex.

The Handmaid's Tale
by Margaret Atwood (1985)

Near-future tale set in the oppressive Republic of Gilead, where the few women left that can still give birth ('Handmaids') become virtual slaves of the state. Offred is assigned to a powerful military leader and the relationship gets complicated. Atwood has crafted a vital story about a woman's right to be in control of her own body.

Dawn [Xenogenesis:I]
by Octavia Butler (1987)

Aliens with ulterior motives rescue some humans from the nuclear holocaust. They turn out to be genetic traders who want to gain control of humankind's DNA through what amounts to rape. Writing from a black feminist perspective - Dawn is a fascinating examination race and gender issues. First book in the superb Xenogenesis series.