Take a look at Lois McMaster Bujold’s Vorkosigan series. I believe the first one published was Warrior’s Apprentice
If you like comedic sci-fi, try Robert Asprin’s Phule’s Company. The first 2 books I really like. After that they added a second author to the books, and I don’t think the series is as good from then on.
I can’t praise The Briar King with nearly the force it deserves. It’s a wonderful book.
zev_steinhardt: The best fantasy series I’ve probably ever read is the Abhorsen Trilogy by Garth Nix: Sabriel, Lirael, and Abhorsen. Just spectacular. It’s sometimes called a young adult series, but every adult I’ve ever handed it to has been wowed. It’s dark, often creepy, with a small bit of humor. Intense and wonderful.
DeadlyAccurate, I’ve never heard of Holly Lisle. Since you like Keyes, though, I’m adding it to my “must read” pile.
Gene Wolfe: The Book of the New Sun tetralogy. Can be found in paper as a single volume, as two double volumes (Shadow and Claw and Sword and Citadel) or as four individual volumes (Shadow of the Torturer, Claw of the Conciliator, Sword of the Lictor, and Citadel of the Autarch). Dark (very dark) fantasy, adult and literary in style, and endlessly fascinating.
For something a bit lighter, Robert Silverberg’s Lord Valentine’s Castle is a good one.
I’m going to add that Garth Nix trilogy to my wish list. Another friend, with whom I share a fondness for similar fantasy novels, recommended it, but I never got around to trying it.
I second Robin Hobb’s three trilogies (though I still haven’t read the most recent one in the third trilogy; I’m waiting for pocket paperback).
You might check out Anne McCaffrey’s Freedom series . It contains no dragons and is more sci-fi than fantasy. I love the main character.
I’d also recommend Elizabeth Haydon’s Rhapsody . I know there are three other books in series after this one, but I haven’t read them yet. Rhapsody was fantastic high fantasy with some dark elements, and some laugh-out-loud bits.
I’d avoid JOB if you have never read any other Heinlein. His later works (of which JOB is one) were, shall we say, an aquired taste.
Check out The Moon is a Harsh Mistress. Or Double Star. Or my personal favorites, Space Cadet and Citizen of the Galaxy.
Yes, Heinlein coined the term “Space Cadet”.
I’d also second Glory Road and Puppet Masters.
I second the Perdido Street Station book–it’s the best fantasy I’ve read in years, and I read a lot of fantasy, working my way through every year’s World Fantasy Award Winners among other books.
Phillip Pullman’s His Dark Materials series (The Golden Compass, The Subtle Knife, and The Amber Spyglass) were, several years ago, the best fantasy I’d read in years :). Although they’re marketed as children’s books, that’s just stupid marketing: they’re full of ideas that adults can appreciate. A warning: organized religion doesn’t come off very well in them.
Daniel
Well, I’d recommend David Brin’s Uplift series. And I’ll recommend anything by Loren Coleman, because he’s a cool guy, though most of his stuff is serialized for Battletech (a RPG/WG) fiction.
I would also suggest the Feist books. I’ve read them a couple of times and they are great. I also loved his book Faerie Tale which is also fantasy but set in modern day America.
I don’t read much science-fiction but I did just finish the Eden series by Harry Harrison. The thought that went into developing “organic technology” that one of the races possesses is very cool.
Head over to the literature section of the bookstore and see if they have a copy of Jurgen, by James Branch Cabell.
In the F/SF section:
Anything by Dunsany–I think a couple reprints of Dunsany might be available in chain bookstores.
Anything by James H. Schmitz.
The Incompleat Nifft, by Michael Shea.
Tales of the Dying Earth, by Jack Vance.
A few of my favorites.
Sci Fi:
Night’s Dawn Trilogy by Peter F. Hamilton - Epic, sprawling Space Opera
Revelation Space series by Alastair Reynolds - Hard SF. I’d actually recommend reading his second book Chasam City before Revelation Space
Hyperion by Dan Simmons and the rest of the Hyperion codex.
Souls in the Great Machine, The Miocene Arrow & Eyes of the Calculator by Sean McMullen are a good read as well
For sheer fun & lots of purple-prose you cant go past E.E. ‘Doc’ Smith’s Lensman books
Fantasy:
Malazan Series by Stephen Erickson - Starts with Gardens of the Moon (I think these have just started being published in the US).
Farseer/Assassin books by Robin Hobb
Another votte for Perdido Street Station as well.
If you liked “The Man who Folded Himself”, there is a Heinlein short story (his short story anthologies are usually pretty good, I think this one is from “The Menace from Earth”) called “All You Zombies”, which has a similar plot executed in far fewer pages.
I’m a fan of Heinlein, Bujold, and Davis Weber. On the less technical end of Science Fiction is James Alan Gardner. Each book is stand alone in that you don’t need to read them in order but there is some cross talk between them in terms of characters/alien critters and such.
I’ve enjoyed Tanya Huff’s Valor Series (Valor’s Choice, The Better Part of Valor). They are space military books but with a fair bit of both humour and tactics with strong female lead.
On the darker end of things is Stephen R. Donaldson in both fantasy and SF. The Gap series is one of the darker things I’ve read. Give “The Real Story” a shot. If you like it, the rest of the series builds from there. If not, it is a short book and a complete story in itself.
Wil McCarthy does a decent story “Bloom” based somewhat on Conway’s Game of Life.
If you do find yourself enjoying Heinlein’s later works, try “Steel Beach” and “Golden Globe” by John Varley.
Two of Jennifer Roberson’s series “The Cheysuli Chronicals” and “Sword Singer” are also worth a shot if you are into fantasy.
-DF
Bujold! Bujold!
And how about Terry Pratchett?
Try Daniel Hood “Scales of Justice” series.
Tanya Huff “Summon the Keeper”.
Barry longyear “Circus World”
“Lord darcy” by uh, erm 
Lawrence Watt Evans “Misenchanted Sword” “With Single Spell” and others in that series.
Simon R Green “Blue Moon series” and “Nightside” series.
Pratchett isn’t for everyone- but even if you find his Adult fantasy a bit off, some think that his kids fantasy (“Amazing Maurice…”, “Wee Free men” & a sequel just out) is still good.
TERRY PRATCHETT!!!
In SF, I heartily recommend the “Sten” series by Chris Bunch and Alan Cole. It really isn’t a series as much as it is a 7 volume novel. Very good!
Any early Heinlein is worth reading several times a year. Also good are the works of Spider Robinson. Dive into the “Callahan’s” books, and try not to rip a stich laughing. 
A second on Steel Beach.
Also Varley’s Gaea Trilogy: Titan, Wizard, Demon.
i might suggest Connie Willis. Esp. Doomesday book (sci fi) and Bellwether. The latter is one of the funniest books I have ever read. It is as good as the end of Huck Finn or the best of Terry Pratchett’s footnotes.
Walter jon williams has three farce Sci Fis that are funny, too. The House of Shards series.
The best hard sci fi that I’ve read is by Allan Steele. He is a NASA toady, but writes well and has good characters.
Rats. Why does Cafe Society get all this juicy book threads?
Oh yeah. Because that’s what it is. Dang.
Moving this on over…
TVeblen
[BTW, another enthusiastic endorsement for Connie Willis. The woman can’t write boring. Bellwether, Lincoln’s Dreams, Fire Watch and Passage come to mind for good starters. ]
I guess Snow Crash or The Diamond Age by Neal Stephenson would count, loosely, as sci-fi. They were groundbreaking when they first came out.
I originally considered recommending The Chronicles of Thomas Covenant The Unbeliever by Stephen R. Donaldson (an author mentioned above). But you didn’t get into The Lord of the Rings, so I’m not sure this would fly either. (However, your not liking The Hobbit doesn’t necessarily mean that you wouldn’t like The Lord of the Rings… The Hobbit isn’t nearly as dark - it feels more like C.S. Lewis to me in retrospect.)