Lord of Light by Roger Zelazny is great.
I’m sorry, the winner is …
The Chronicles of Amber, by Roger Zelazny
fits your likes to a tee !
The Sparrow andChildren of God by Mary Doria Russell are both amazing. Yes, there are aliens, but the heart of the story is about a Jesuit priest named Emilio Sandoz who is sent on the first mission to another inhabited planet. He is the only survivor of the mission and the story is told in flashbacks. Sandoz’s story depicts just about the worst trial of the soul a person could ever endure, with of course a kick ass ending. Simply amazing.
Also, definitely listen to everyone who has mentioned Dune and Foundation. I also liked Asimov’s I, Robot series.
Judging by what you have said, RitzyRae, you may be more interested in Fantasy then Science Fiction.
I have heard the Novelizations of the recent Lord of the Rings movies are pretty good… 
A book I am reading now is Songs of Earth and Power by Greg Bear. It concerns a 16 year old Boy from L.A. who becomes stuck in the realm of the Sidhe, an ancient pre-human malevolent race. The concepts are fresh and the writing is top-notch.
Bear is better known as a writer of hard SF, but he aquits himself very well in this foray into fantasy.
I’ll second the vote for Lois McMaster Bujold’s Barrayar series. Strong characterization, good plots (intrigue!), well-built societies. The writing is not quite as strong in the first couple of books. It gets much better.
Thanks Larry Borgia! I’d almost forgotten about the few fantasy novels I had read years ago and enjoyed. I may venture into that section once again…
If you like Arthurian legends, you’ve probably read The Mists of Avalon, by Marion Zimmer Bradley.
You might like the Dragonriders of Pern series (first three books) by Anne McCaffrey. It’s borderline sci-fi/fantasy, and is about a pre-technological society.
Connie Willis’s novels are good borderline sci-fi. The Domesday Book deals with time travel back to the time of the Black Plague in Europe. To Say Nothing Of The Dog deals with time travel back to Victorian England.
Listen to the people who said Roger Zelazny The Amber Series is Arthurian as you can get. Plus he’s a wonderful writer. He was a wonderful writer. And if you ever want to understand any mythology read Lords of Light, Children of LIght and Darkness, etc. In fact go to the library and just check out Zelazny. You’ll be busy for years. . . 
Since others have covered science fiction recommendations so admirably, I’ll concentrate on fantasy that you might like, Ritzy.
Mercedes Lackey seems to fit your criteria pretty well–her main series spans roughly 3000 years, but most of the trilogies stand on their own pretty well. They feature lots of magic of various kinds, interesting magical beings, and personable characters–in fact, I’d say Lackey’s greatest strength is in writing characters that you can identify with easily. Caveats: The second and third books of the Gryphon trilogy are much weaker than the first, and Brightly Burning and the Last Herald-Mage trilogy are (IMHO) depressing.
Steven Brust is another favorite of mine, particularly his Vlad Taltos novels. They center around a human assassin in an elven empire. Vlad is surprisingly easy to root for, given his profession, and the books are loaded with devious plots, magic, sharp pointy things, and sarcastic familiars. They’re quick, fun reads. Brust’s Paarfi of Roundwood books are much less accessible, being longer and written in the most extraordinarily circumlocutive style (Ex: Chapter the Thirteenth, In Which the Plot, In Much the Manner of a Stew to Which Cornstarch has been Added, Begins at Last to Thicken). They’re fun if you like playing complicated games with language.
P.C. Hodgell’s work–Godstalk, Dark of the Moon, and Seeker’s Mask–features dark conspiracies, strange magic, inscrutable gods, and dark humor set against a rich historical background. I could ramble about these books all day, but I’ll leave it at this: They are my favorite fantasy works, period.
I also second the recommendations of Zelazny’s Amber.
Seriously everyone, this has been wonderfully helpful and I’m listing out all of your suggestions.
Now I just need to quit work, end my social life, and move in to a library for the next few years!
Consider the Moreau novels of S. Andrew Swann.
Forests Of The Night.
*Emperors Of The Twilight.
Specters Of THe Dawn.*
And there’s a conveinent Omnibus edition.
Great series! 
Geeze, no one’s mentioned His Dark Materials by Philip Pullman yet? Look into giving it a shot; sometimes the books are in the young adult section (both library and bookstores and wrongly, in my opinion), sometimes in the adult fiction (library), and sometimes in the science fiction (bookstores).
That’s the Culture series right there, if anything. GREAT action and adventure, but not pompous or overdone. Excession and Look to Windward are fucking amazing in the “murderous conspiracies” category. And you can’t get much more interesting than a Culture Mind. And some of the technology mentioned is so fantastic - yet, when you think about it, it makes sense - that it seems pretty damned magical.
Start with Consider Phlebas, but like Matthias said, it’s not too terribly happy a book. Personally, I think Look to Windward and Excession are the best… the latter contains the only scene in any book I’ve ever read that literally made me have to stop and take a few minutes to compose myself, it was that powerful and mind-blowing (for those of you that have read the book, it was the climax of the flashback relationship between Dajeil Gelian and Genar-Hofoen).
Some that have not been mentioned so far
Eric Flints 1632 series of books , two so far , one to be released sometime in the next year
Philipe Jose Farmers riverworld series , most serious sci/fi buffs will have this one on the permanent bookshelf , much thumbed.
and another plug for Lois McMaster Bujold , she does sci/fi for the rest of the world , if there was a scifi coin , David Weber would be on one side ,and lois would be on the other.
Declan
My favorite SF series are the Liaden Universe novels by Sharon Lee and Steve Miller. They’ve got fights, space battles, romance, a mysterious organization plotting to take over the world (not Earth, though) and even a bit of magic.
For fantasy, I’ll second the Steven Brust Taltos novels. And also suggest the Sacred Hunt and Sun Sword series (both of these are set in the same world) by Michelle West.
If you like humorous novels, you should check out the Discworld series by Terry Pratchett.
Not sci-fi but not fantasy either, try the Deryni/Saint Camber series by Katherine Kurtz. sort of like an alternate medival Europe where magic works. The magic is portrayed in a realistic manner consistant with the times. The books deal more with politics and characters than magic.
Anything by Turtledove sounds right up your alley.
Run, do not walk, to your local book purveyor (library, used book store, Barnes & Noble, etc.) and obtain copies of The Mote in God’s Eye and The Gripping Hand by Niven and Pournelle. Then read them.
Just MHO, of course.