If you are at all interested in history, as well as science-fiction, try 1632, by Eric Flint. It’s time-travel with a twist. Instead of just one person getting thrown into the past, it’s a whole town that’s plunked down into the middle of the Germanies during the 30 Years War. If you like it there are already sequels, two novels and a book of short stories. In the latter book, Ring of Fire, “The Wallenstein Gambit” might interest you particularly.
I agree. Not that it feels much like Lewis to me, but The Hobbit is a lesser book all the way around, in my opinion, than Rings. Shorter, shallower, and with a whole lot of interchangeable dwarves with rhyming names.
I didn’t read The Hobbit until decades after reading Rings, and didn’t enjoy it nearly as much.
Considering the books zev has listed as likes and dislikes, I wouldn’t suggest Donaldson. He didn’t like what he read of Tolkien and didn’t like Herbert, and for some reason that rules out Donaldson for me. I’m weird.
But I forgot to recommend a few of the older Trek books. zev, do you only like TNG? I think the better books tended to be written for TOS. Some weren’t really “canon,” but there are some truly great books written for TOS, like Dwellers in the Crucible, The Entropy Effect, the Diane Duane books, and (most of all) The Final Reflection. Just avoid the hell outta some of those old books. You’ll regret reading any of the Marshak/Culbreath combos, for example.
Neil Gaiman - American Gods, Stardust, Neverwhere(Also available on DVD from the BBC!) - Smoke and Mirrors(his re-telling of Snow White is the best ever). The Sandman (Graphic Novels). He also has a wonderful website.
If you want to try out Terry Prachett, BBC Radio4 is doing a dramatization of “Mort” in 4 parts. You can listen to it on their website. It’s a riot!
The Ethshar Series by Lawrence Watt-Evans.
This is pleasant light fantasy. The first book in the series is The Misenchanted Sword. Reading one of these books always puts me in a better mood.
One offs:
Split Heirs by Lawrence Watt-Evans and Esther M Friesner
This is fantasy/humor. Very funny.
The Case of the Toxic Spell Dumpby Harry Turtledove
I love this book. Harry Turtledove is the best premise guy out there. The premise behind this one is that there is a world, about as modern as ours, but the technology is magic/supernaturally based. There is a EPA (environmental perfection agency) inspector trying to find out if there is a leak in a toxic spell dump that is causing problems. Just like the by products of current manufacturing creat pollutants, so do the magical one. Great puns–for everything we have, in this world there is a magical/supernatural based equivalents. For example, spies are real spooks/spirits of some sort. Interesting also because religion is so important in this world. The main character is Jewish, which does enter into the story.
Lynn got me hooked on Terry Pratchett. He’s hilarious, and thoughtful. And addictive.
On my own I’ve stumbled across…
Robin Hobbs. She has several series, all somewhat interconnected, but they’re all absorbing reads. She does a great job of complex world building and character development.
Steve Miller and Sharon Lee, notably their Liaden universe series, though the others are good as well. It’s finest-kind space opera, with much insightful stuff tucked along the way. There are collections available now, but the basic titles are Conflict of honors, Carpe Diem, I Dare, Plan B. Compulsively readable, and unusually vivid writing.
Lois McMaster Bujold, especially her Vorkosigan series. It’s the one which finally somewhat lured into SF/fantasy years ago, with a glowing reviews of Shards of honor. She does an unusually cohesive job of blending science, engineering, religion and social speculation while telling a helluva great story. She’s been branching out into fantasy lately–Curse of Chalion, Paladin of Souls but they’re unusually tough-but-high-minded and very human. Great stuff.
And Connie Willis bears repeating…again and again and again. If you read nothing else, read Bellwether (hilarious, pungent and always relevant), To say nothing of the dog (Edwardian literature, time travel, dizzying interconnectivity and…oh, hell READ it), Doomsday book (harrowing but wonderful) and Passages about the possible nature of death, the Titanic, and so much more. Stellar reading.
Veb
Try Tad Williams’ Memory, Sorrow, and Thorn trilogy. Outstanding character development and a beautifully rich setting have made these books my favorites since high school. They’re just amazing.
I don’t know how you feel about hard sci fi, but try Charles Sheffield. Anything, really, though Tomorrow and Tomorrow is really good.
I’ll second the recommendations for the Amber series, and, of course, Terry Pratchett.
Guy Gavriel Kay does great sort-of-fantasy. They’re not really fantasy book so much as almost alternate reality books. Each book, or series, is set in a mythical land that’s loosely based on some real place and time in European history. The Lions of Arbonne, for instance, is set in a land that’s similar to Spain/Portugal during the time of the Moorish reign. Tigana is basically in medieval Italy, when it was still made up of warring independent states. There are occasional fantastical elements thrown in - your odd sorceror or whatnot - but they’re usually in the background. My personal favorite is Sailing to Sarantium and its sequel, Lord of Emperors, which is based on the Byzantine Empire.
And I have to recommed The Cryptonomicon, by Neal Stephenson. It’s not really sci-fi, but you’ll find it in the sci-fi section, because Stephenson has been pigeonholed as a sci-fi writer. It is, quite simply, the best book I’ve read in at least 5 years, and I read probably close to a hundred books a year. I’m anxiously waiting for my too-helpful memory to forget enough about it so I can reread it.
Most of the things I would have suggested have already been named - Bujold, Feist, the Amber books, anything by Greg Keyes (he has also published under J. Gregory Keyes), excellent suggestions. I haven’t managed to read anything by Guy Gavriel Kay yet, but I’ve heard good things about him. However, I would like to add The War of the Flowers by Tad Williams. It’s a standalone fantasy book, neither particularly light-hearted nor particularly dark. It has one of the more original Faery worlds I’ve seen.
Also, you’ve heard correctly about Eddings’ newer fantasy. Don’t read The Redemption of Althulus unless you want to read a book full of almost nothing but Polgaras.
I am, of course, a big fan of CJ Cherryh’s Foreigner books. Cherryh isn’t everyone’s cup of tea, but I think these are fantastic.
I also want to heartily second the Vance recommendation, and suggest his Demon Princes books, or the Alastor books, both available in omnibus (omnibusses? omnibi?). You won’t regret having read any of them.
I recently ran across James White’s Sector General books, and have very much enjoyed the ones I’ve read.
Bujold is good, the Liaden books are fun (even though I nearly put the first one I read down because the opening was lame–I mean, Starhawk? Give me a break) But I’m glad I finished it.
Heh. Add Heinlein and Brust to that, and we’re in complete agreement.
With Bujold, start with Borders of Infinity–it’s not her best, but here’s the thing. You have to read the series in order to understand and appreciate the wonderful later ones but she’s writing them in chronological order and therefore the earliest are her least polished. Borders is a nice compromise contains three novellas that’ll give you a taste of how good Bujold can be (although it doesn’t showcase her sense of humor. keep in mind that this is a dark book for her) and then you can go back and start at the beginning.
Pratchett–There’ll be a huge fight about where to start, but I recommend Small Gods. It’s not as good as some, but it’ll give you a taste and it’s a stand-alone (there’s like four series that take place within the Discworld uber-series).
Heinlein-Moon is a Harsh Mistress, Tunnel in the Sky
Brust–Jhereg to start.
Connie Willis–To Say Nothing of the Dog. Funny, thoughtful, wonderful
And, if you like Foundation and Baxter, you’ll like Larry Niven (start with Tales of Known Space and Neutron Star and Vernor Vinge. Specifically A Fire Across The Deep. The premise: The galaxy is divide up into zones. The first zone (closest to the core) is the unthinking area. People get dumb there. Then there’s the “Slow Zone”: computers can’t become sentient, faster than light travel doesn’t work (we’re at the edge of this area). In the next area, FTL works and computers can become sentient. Finally at the edge of the galaxy (the Transcend), there are Star Trek Godlike aliens, etc. Magic-tech works. The story opens with some “archeolgists” exploring in the Transcend and unleash a super computer virus-like thingie that works on human brains. Oops. They rocket the “anti-virus” off with their kids as the virus (The Blight) and all the remaing free people scramble to get at it. It’s probably in my top ten SF books of all time.
Fenris
I’d recommend looking at the other books by some of the authors you’ve already read and liked.
Stephen Baxter’s Manifold series, for example, might be up your alley.
If you do decide to pick up Ender’s Game by Card, I’d recommend getting Armor by John Steakley.
And if you go for those two, get Heinlein’s Space Cadets and Starship Troopers which share similar themes. 
I’d definitely second the recommendations for Terry Pratchett (though I’m not sure which book I’d pick to read first) and for Bujold’s Vorkosigan series.
A few others which haven’t been mentioned - some of them are older, and you may need to find them in a used book store:
Cordwainer Smith’s Norstrilia and “Instrumentality of Man” stories. Very strange universe, and well written stories. “The Ballad of Lost C’Mell” is one of my strongest early SF memories, set on an Earth in which humanity is just beginning to recover from an era of “perfection”, much of Earth’s work is done by underpeople warped from animal stock, and the Instrumentality of Man rules largely through indirection.
S. Andrew Swann, “Forests of the Night.” A genetically engineered private eye (tiger stock) struggles to survive in a world where Moreaus are only marginally tolerated. Alternates between funny and grim (a gunfight involving a fox, a bear, and an Afghan hound?)
Larry Niven and Jerry Pournelle, “The Mote in God’s Eye.” The second galactic empire encounters a highly intelligent race locked in a single solar system.
Barbara Hambly: “Those Who Hunt the Night” and “Bride of the Rat God.” Both are fantasies; the first is set in a sort of post-Kipling England, and the second in 1930’s Hollywood. To my mind, Hambly is uneven; but these are very good.
Tim Powers, “The Anubis Gates.” Time travel to 1800’s England, through gates opened by a sinister magician out of ancient Egypt. I haven’t been able to get through some of his later books, but I very much like the earlier ones.
Glenn Cook, “Sweet Silver Blues.” Private eye Garrett in a grimy fantasy world. After the first few books the series deteriorates, but the first three or four were well worth reading.
C. J. Cherryh, “Pride of Chanur.” What Star Wars should have been - great “Space Opera” adventure in a pocket of near-earth space where humans are the aliens. If you like it, there are several sequels, all good.
Thank you! I had that Powers book recommended to me before, but had forgotten about it. Puttin’ it on the list.
I recently read my first non-Star Trek Hambly and enjoyed it a lot. But the name escapes me. Desert world where only men can do magic, the rains stop, women start being able to do magic, plot involves a girl, a prince, and the prince’s consort? Is this ringing a bell for anyone?
Oh my goodness, I didn’t expect this kind of response. Thank you everyone.
On Friday afternoon I went out and took several of the titles mentioned earlier in this thread to B&N. After much careful consideration, I ended up with The Briar King.
Once I’m done with that, however, I will go on to others recommended here. Thank you all so much.
As for your suggestions:
I tried Donaldson’s Covenant series a few years ago. As others have figured out, it wasn’t my cup of tea.
I read some Pratchett years ago, but lost track of it a while back.
Baker, as you can probably tell from the Turtledove titles on my list, I am a fan of alternate history. I’d been meaning to try 1632 for a while now, but I never got around to it. It sounds similar to Stirlings “Sea of Time” series.
jsgoddess, I am a real ST fan, including TOS. The only TOS book that I read that I liked, however, was Ishmael.
lee, I’ve seen the Toxic Spell Dump in the stores, but it didn’t seem to interest me at all. However, the world you describe sounds a bit like Piers Anthony’s Incarnations of Immortality world (where science and magic operate side-by-side).
Fenris: I actually started to read Ringworld once, but it seemed kind of slow. I put it down intending to pick it up a bit later (I do that and sometimes it works for me – I’ll get into the book on the second or third try) but never got back to it.
Thank you to everyone who made recommendations and please feel free to keep them coming (although I can’t read that fast).
Zev Steinhardt
I don’t know if you’ve ever read anything by her, but I’ve enjoyed everything C.S. Friedman has written. There’s a fantasy trilogy and three (or so?) sci-fi standalones.
I have to second Snow Crash by Stephenson, which was mentioned earlier. I haven’t been able to get into Cryptonomicon yet, but I hear it’s quite the read, and it seems like it might be up your alley.
Otherwise pretty much just the same as above, though I feel better about some of the aforementioned than others.
-K.
Ringworld (and progressively abomidable sequels) are the last books in the Known Space series and are (IMO) the weakest book(s) in the series as well. IMO, Ringworld is famous because it featured some neat ideas, not because it was all that good. I’d really recommend you read some other Known Space stuff first. (Besides, there are a couple of big revelations about the backstory of Known Space that won’t mean anything unless you’ve read the earlier books first)
Fenris
Ender’s Game is a must.
I though “Small Gods” was one of his weakest, and it didn’t have any of the main characters (Granny, Vimes, and Rincewind). It is also a pretty heavy-handed attack on organized religion, so… Which is why I’d start with his “kids” fantasy. There are really three “series” and some dudes like the “witches/Granny” track but don’t like Rincewind, etc.
I picked up “Jhereg” and hated it before I even opened it- the idea of an assassin being the “hero” (and which he later turns out to be) has been SO overdone. Oddly, I read “Phoenix Guards” and loved it (and the sequel not quite as much) so I then went back and read Jhereg. Jhereg is likely the worst of the series, although it is the first. Still, the idea of a “heroic killer for hire” is stupid and over-used.
For Niven I’d pick “Inferno” meself.