Spin State, by Chris Moriarty - strong female lead, incredibly enjoyable science fiction book that I had a hard time putting down.
David Drake’s Lord of the Isles series. Two of the four main characters are very strong women, but definitely women. Ilna is amazing.
Also second Dave Weber’s Honor Harrington books.
Some of the dragon riders of pern stories certainly have very strong female characters
Darn you all, my suggestions have been made. But I will put in good words for Robin Hobb’s Liveship Traders series (her other series don’t have many female characters in lead roles), Melanie Rawn’s Dragon Prince and Exiles series, George RR Martin’s Song of Ice and Fire series (he writes the best 9 year old girl I’ve ever seen in adult literature), and I will add my own recommendation of Margaret Weis’ Star of the Guardians series.
If you’re tired of european/western themed fantasy, you might like to try the following:
Leopard’s Daughter, by Lee Killough, African fantasy
Ladylord, by Sasha Miller, vaguely asian-themed fantasy
the Tomoe Gozen trilogy by Jessica Amanda Salmonsen, Japanese fantasy
Paper Mage, by Leah Cutter, Chinese fantasy
The Caves of Buda, by Leah Cutter, vaguely Hungarian w/hints of Romani fantasy
The Devil Wives of Li Fong by E. Hoffman Price, Chinese fantasy.
And finally, since I’ve not seen anyone else bring this one up, the Queen’s Quarter Knot tetrology, by Midori Snyder.
I get in trouble from my husband for buying too many chick books. 
He says he’d like one with a male protagonist for a change. I tell him he needs to go buy his own then. 
Okay, just my two cents:
I find Anne Mcafferey’s early books to be very sexist. I read them when I was a kid, and then picked them up again a couple of years ago. Woah! The major female characters seemed to spend all their time worrying about the men in their lives! I can still remember the part where Lissa has just returned from her long journey, and F’Lar shakes her, he’s so upset. All she can say, while crying, is that she knew he would shake her! I’m not explaining it very well, but it just left me cold.
As for George R. R. Martin, I just find him way too quick to use rape as a little side joke, or just as a completely unnecessary background to the main story.
YMMV, of course.
I would second Tanya Huff, definitely, Mercedes Lackey, Anne Bishop, and Melanie Rawn. Also, David Weber, Catherine Asaro for more military sci fi, and Laurell K. Hamilton, if you can handle all the sex, for vampires and were-creatures.
Just re-read, and realised Phouka made the same point about Mcaffrey half a page ago. Sorry!
I second (or third…) the recommendation for Robin Hobb’s Liveship traders. Also George R. R. Martin’s a song of ice and fire series (catelyn, arya and malisandre… - although you’ll hate sansa:))
I think someone objected to Robert Jordan in this context since most women in that series are brainless ninnies (yes, I’m looking at you nyaneve) - but the series itself, well… I like it, although yes, it’s dragging out by now.
Tikster
I droped in here to specifically recommend David Weber and James Alan Gardner, totally forgot about Tanya Huff. So now that my thunder has been stolen, how’s about I narrow a couple of recommendations down?
The James Alan Gardner series has a different main character in each book and each is set on a different world (well, Earth has appeared twice). You can read them in any order, but some critters and social constructs/rules are developed as the series progresses. Festina Ramos, the protagonist of the “Expendable” also appears in all but the second book so your best bet is to start with Expendable and then go exploring. My personal favorite of his books is “Vigilant” (Book 3) and it happens to fit exactly what you are looking for.
The only Tanya Huff I’ve read is the Valor series, about Staff Sergeant Kerr: confident, competent and lethal. It’s two books so far (Tanya, when ya got some time can we PLEASE have another?) both very enjoyable, especially if you’re into military Science fiction.
-DF
To defend Jordan a bit (just a bit!) it’s not so much that his women are brainless ninnies. It’s that all the heroes are brainless ninnies. Both the men and the women. (Mat, Perrin, and Rand can out-ninnie Nynaeve any day of the week!) Jordan does, however, have a very visible fascination with bosoms. (A fascination I share, but don’t write about.) (except just now, apparently.)
Wow, I am glad I get to slip in and mention CS Friedman.
Anzha lyu Tukone is terrifying in In Conquest Born. Jamisia from This Alien Shore is also a downright badass. Her women are strong not due only to their combat prowess but to their limitless grit and resourcefulness. Enjoy!
The Black Swan by Mercedes Lackey was a good read, with several female characters who are strong in their own way. Tanya Huff also has a duo in Child of the Grove and The Last Wizard that I absolutely adored, I highly recommend them for the strong female protagonist and the engaging story.
[Hijack] By any chance is Anduin your real name? I’ve never heard anyone go by the name of Tolkien’s river except for a friend of mine from childhood.
Daniel
Titan Wizard and** Demon** by John Varley. The character Sirrocco Jones always reminds me of Ripley/Sigourney Weaver .
That’s who I was going to suggest. Actually Kindred is her only book (that I know of) that I havn’t read.
The Patternist series (Wildseed, Mind of My Mind and Patternmaster) is good and has strong female characters but a little more far out than some of her other works (it’s basically about what would the world be like if there really were super powers).
Parable of the Sower and Parable of the Talents are excellent. In fact Parable of the Talents is the only book I had to stop reading because I got too emotional reading it. I finally went back and finished it.
I’ll admit, Clay’s Ark and Survivor aren’t as good as her other books. They are in the Patternist continuity but aren’t really a part of it. Clay’s Ark is important to Patternmaster, but not to the other books.
Forgot to add another suggestion.
Joan Vinge’s Snow Queen and Summer Queen. There’s actually a bopk that goes between these two called World’s End, but it’s not very good and the only two plot points that matter in the third book are talked about in the first few pages.
The Snow Queen is one of the first sci-fi books I ever read that I got pulled into the characters as much as the story. The characters are very diverse, strong and weak males and strong and weak females. And a robot.
I forgot Anne Bishop’s Black Jewels Trilogy. The women rule over the men, and one of the main tenets of the book is watching a few adolescent girls grow up from awkward teens into strong, capable women that can help shape the world for the best.
No, unfortunately, it’s not. But it was the name of a friend of mine in high school. Was your friend an Air Force brat, by any chance?
Oh, and just so this is isn’t a complete hijack, I second C. S. Friedman. The two books previously mentioned rock!
Hey, I was gonna say that one! Danica definitely kicks ass – and she’s a very independent type, as well as physically agile and adept at fighting sans weapons.
For Sci-Fi, I recently read one called Mainline, by Deborah Christian. Main character is a woman named Reva. Strong in many ways, and some of those strengths are weaknesses in other ways – i.e. she’s independent, strong, confident, and a skilled assassin. Some of that ends up being a weakness in that it has prevented her from being able to keep any lasting friendships with people, so she is also somewhat lonely and detached from her human side.
Sharon Lee and Steve Miller: the Liaden universe series.
Melissa Scott: the Roads of Heaven series.
Holly Lisle
Elizabeth Scarborough.
Phyllis Ann Karr
Phyllis Gotlieb
Suzy Mckee Charnas
Marta Randall
Suzette Hadan Elgin; her Coyote Jones series, her Ozark series, and especially the Native Tongue series.
The Sword and Sorceress anthology series, edited by Marion Zimmer Bradley, is a nice sampler of fantasy with female protagonists.
And I want to second the mention of James H. Schmitz. He is particularly noteworthy in that he was a man writing in the '60’s. I found his books a good antidote for all the “woman as object to be rescued or excuse for the action” books around.