Alessan already reccommended Guy Gavriel Kay, but I am going to specifically suggest The Fionavar Tapestry, which is broken up into three books; The Summer Tree, The Wandering Fire and The Darkest Road. All of the characters, including the women, are three-dimensional and, in the end, fully realized. The story is crushingly heartbreaking and breathtakingly beautiful, inspiring and triumphant.
Some people find it too derivative of LOTR, but I say those people are shallow and simple-minded. 
I second the William Gibson recommendation for Neuromancer and also offer up his book Virtual Light - Chevette Washington is no slouch either.
I dunno—strong and experiences personal growth, sure, but she still seemed fairly grating and bitchy on top of that. (It makes the character more realistic and “human,” though.)
I have an art book called Firebrands by Ron Miller lying around, somewhere, that features a lot of the more interesting heroines from scifi and fantasy over the years. Though not a few of the paintings feature the characters is states of undress ( :smack: ), it still might be a good place to look for suggestions for reading material.
Lisa, in Turning on the Girls by Cheryl Bernard.
Fiametta, in Lois McMaster Bujold’s The Spirit Ring
Jame, in P.C. Hodgell’s God Stalk
How 'bout Octavia Butler? I just read Kindred yeasterday (I couldn’t put it down). Granted, It’s not really SF, except for the time travel, but a lot of Butler’s other works seem to be speculative SF stuff, with lots of strong female characters. I just bought Parable of the Sower. I can’t wait to read it.
ZJ
Phillip Pullman’s His Dark Materials trilogy, for Lyra Silvertongue: very strong female protagonist.
As long as we’re doing the Gibson Girls, Cayce in Pattern Recognition was very cool. She wasn’t super-smart, or some kind of a ninja. She was kind of an average girl with a very strange talent, but tough as nails and—did I mention?—cool.
S.M. Stirling puts a lot of strong female characters into his novels. In fact, they’re not just strong, they’re fierce – formidable warriors in the hand-to-hand combat sense. One of them could eat any Heinlein heroine for breakfast, including Friday Jones. Also they’re often bi or lesbian, and sometimes aristocratic. He seems to be really fascinated with the Warrior Woman. See his Domination of the Draka series, Fifth Millennium series, and Nantucket trilogy.
About McCaffrey – I’d suggest staying away from her Freedom’s Landing series if you’re seeking realistic characters. The two main characters are both TOO good to believe. I kept waiting for one of them mess up or to have an argument or do something wasn’t so goddamn noble. After the first book, it focuses more and more on the male protagonist, and you just keep waiting for the female protagonist to talk about something besides her concern for her husband. Blech. She certainly is a strong female character, but at the same time she’s a modern paragon and a leggy blonde to boot. She’d be so much more believable if she had acne or made mistakes or had to deal with jealousy or something.
Zjestika, Parable of the Sower is excellent. One of my friends had to read it for a gen req class last semester and he was pleasantly surprised by it. That book completely changed his mind about the course being a waste of his time, like so many gen reqs seem to be.
Esther Freisner’s Chick series is filled with strong female characters:
Chicks in Chainmail
Did You Say Chicks?!
Chicks and Chained Males
The Chick is in the Mail
Turn the Other Chick
Anything by Juliet Marillier (starting with Daughter of the Forest).
Elizabeth Haydon’s Rhapsody series is well-regarded (I haven’t read it myself).
Neal Stephenson’s cyberpunk novel Snow Crash or William Gibson’s Mona Lisa Overdrive.
Maria Doria Russel’s The Sparrow. An excellent book. Also the sequel, Children of God.
In recent Science Fiction Singularity Sky by Charles Stross has a central strong female character (not the main or only character, but important). Also the sequel Iron Sunrise.
Also recent, a novel by Louise Marley called The Child Goddess.
What do poeple have against Robert Jordan? Well, he’s a hack, his wife edits his books (danger Will Robinson!) and consequently they are about 5 times too long for the story they tell… the series keeps getting longer and longer and longer and doesn’t seem to be in any danger of finishing any time soon… basically a trumped-up Tolkein rip-off artist who’s going to milk his franchise till it runs dry, bone dry.
But don’t ask me… I don’t have an opinion either way. 
In recent years Anne McCaffrey has REALLY been phoning it in, but personally, I think even the early Pern stuff is kind of cheesy. Of course, I think that about the majority of Fantasy (and much SF) – and yes, I am a HUGE reader of both, I’m just picky.
Pretty much anything by Octavia Butler is going to have strong female protagonists: Rane Blake of Clay’s Ark, Anyanwu of Wild Seed, Lillith Iyapo of the Lilith’s Brood trilogy (also marketed as Xenogenesis), Lauren Olamina of Parable of The Talents – and of course Dana Franklin from Kindred, which I first read when I was twelve or so.
If you’re a comics fan {and if you’re not, you could do worse than start here} you should check out The Ballad Of Halo Jones - originally a three part 2000 AD series, but available in a collected trade paperback; Amazon stock it - by Alan Moore and Ian Gibson: some very good Alan Moore writing, and nice black and white Ian Gibson artwork.
Moore wrote it in the early 80’s as a response to the standard depiction of women in comics and sci-fi in general as either large-breasted bimbos, damsels in distress, or Amazons in scanty chainmail bikinis.
Halo Jones is just an ordinary young woman trapped by unemployment in a dystopic “increased leisure” community on a futuristic Earth, which she eventually leaves to face an unknown future in an economically depressed and warring galaxy after the death of a friend - by her own admission she isn’t especially clever, brave, or beautiful {although Ian Gibson is incapable of drawing unsexy women}, and her adventures arise from the situations she finds herself in: she’s an excellent “everywoman” heroine, a breed quite rare in sci-fi. And her clothes aren’t skin-tight and never fall off.
In Stirling’s Nantucket trilogy, in which the whole island is transported back to 1250BC, there are many strong characters of both genders, but a major one is the Coast Guard captain Marian Alston. As she puts it herself, she has several strikes against her, being female, black, and lesbian, but her military and command capabilities save the Islanders several times over, and her threat to resign if certain executions are carried out stops them. Nobody wanted to risk losing her!
I’ll second (or third) Sheri S. Tepper. I just finished reading her The Companions and often re-read her books.
Another author with strong female characters is Janet Kagan. The only title that springs to mind is Hellspark and much of her writing is short stories, so hard to find outside SF magazines and anthologies.
I must expand on the Barbara Hambly recommendation. She writes not just strong women, but strong women and men. She’s extremely even-handed in how she approaches her characters. They are, all of them, three dimensional creatures - flawed, human, and remarkable.
Of her books, I’d recommend the Windrose Chronicles first. These include The Silent Tower, The Silicon Mage, Dog Wizard, and Stranger at the Wedding. The main female character in the first three, Joanna Sheridan, is a computer programmer who gets stuck with a mad wizard and a ticked off ninja, trying to save both her world and theirs from a dark wizard that was executed twenty years previously. Very good stuff.
I’d also recommend Bride of the Rat God, Time of the Dark, Walls of Air, Armies of Daylight, Mother of Winter, and Icefalcon’s Quest. Actually, I’d recommend you pick up anything that has Barbara Hambly’s name on it, including her mystery series.
As for Anne MacAffrey, I used to enjoy her. A few years ago, I went back and recollected her Pern novels. Not even the original trilogy was as good as I remembered. All her heroines are beautiful. Pretty much all of them get mistreated by men - F’lar’s favorite response to Lessa was to shake her - and most of them get rescued by other men. Even Sharra, who was originally described as not beautiful ends up beautiful in a later book. Darn it, I hate it when I go and spoil happy memories of stuff.
Hope you haven’t already been to the library, but here’s my 2 cents:
Most of the books I would recommend have already been mentioned by previous posters, but I’ll add to the chorus for LM Bujold, GG Kay, and R Feist/J Wurts.
Hellspark by Janet Kagan has been mentioned, but she’s also written Mirabile.
Other books with strong female protagonists include just about anything from Tanya Huff and Nameless Magery by Delia Marshall Turner.
Spider Robinson has strong female characters in all his work, who are both strong and complex. Highly recommended.
Robert A. Heinlein also has great female characters, from Grace Cormet in “–we also walk dogs” to Friday, in the book of the same name.
I already do watch Futurama. I’ve read Elvenbane and ended up giving it away to a friend of mine. I was just curious about the Robert Jordan thing. A lot of people have told me not to read him, and when I ask why, they won’t really say, they just get sort of wibbly. I’ve read one McKillip–The Forgotten Beasts of Eld --and enjoyed it. I think my best bet is to check out the library website first before I go there. Our local library has a very uneven selection. Thanks again for the recommendations, and I’m glad that this thread is helpful to others too.