I loved the Name Of The Wind. I can’t wait for the next release. It has been way too long.
I too liked Scott Lynch’s books, but was always disappointed at the end. I will read the third when it comes out, but I keep wanting more.
Some of the ones mentioned are great. In addition, try these:
Mostly anything by Robin Hobb gives me the same “feel” as A Song of Ice and Fire. It’s dark, horrible and anyone can die, and the main characters usually suffer. Assassin’s Apprentice is the first book in a rather kudzu-like series of trilogies.
Judith Tarrs books about elves are great, with a rather strange story, beautifull historical backdrop and interesting characters. I think the first one is either The Isle of Glass or The Hound and the Falcon, I forget which is which.
Want to echo all the recommendations for Tim Power’s books above - although I still like The Anubis Gates the best of all his works.
I know you said you couldn’t get into Perdido Street Station (neither did I, but I finished it), but Mieville’s second book in the series, The Scar, is awesome. It took me a little while to get into it, but once I did I was really hooked. Recommend highly.
I also liked Sunshine by Robin McKinley (ok, it’s a variation on a vampire theme story), first recommended somewhere here on the Dope.
And for true semi-otherworldly somewhat twisted fantasy, you can’t beat Charles Stross’s The Atrocity Archives.
Personally I always liked her Riddle Master trilogy best of her books.
Your tastes sound extremely similar to mine, with the exception of The Name of the Wind. (I couldn’t stand it.) I’ve plumbed some of the more obscure reaches of the fantasy genre, so I can recommend a few that haven’t been mentioned yet.
The High House, by James Stoddard. It is nearly impossible to praise this book too highly. The writing is absolutely excellent, with luxurious descriptions of everything, yet the book also moves along very quickly. It’s basically a story about a child raised in a magical house with dinosaurs in the attic and tigers in the basement. Sound strange? It is, but the writer makes it feel perfectly normal.
The Man Who was Thursday, by G. K. Chesterton. A classic written 101 years ago that never loses its appeal. The story of a policeman who infiltrates a gang of violent anarchists in disguise. The plot is legendary. (You probably know that there’s a book which has this plot, even if you don’t know that it’s this particular book.) There’s humor, suspense, and plain old weirdness all mixed together. I would argue that this is the greatest short novel ever written.
Wizard War Chronicles, by Hugh Cook. Like George R. R. Martin’s series, only better. It’s hard to find these books in America, because they’ve been out of print for twenty years, but scoop them up whenever you get a chance.
Meh. I need more than “not too bad” to recommend a single book to me; if I’m looking at a trilogy, I need it to a helluva lot better than “not too bad.” This is a ten-book series, right? I got 70 pages into the first book and put it down, and see no reason to pick them up again in my lifetime. “Not too bad” is a recommendation for a dental procedure, not for an entertainment option.
Squee!
I meant to mention this one! It’s unique and amazing, definitely worth trying out. It starts a little slow, but it’s got a compelling magical structure, and it builds to a wondrous climax.
Daniel
Soon this thread is going to look like the “goose is greasy” thread. Because I’m going to pile on and recommend it again.
Speculative Napoleonic Wars geekery? Check.
Hints about an incredibly rich backstory? Check*.
A charming narrative voice? Check.
Really good characters who bounce off of each other in a wonderfully period manner? Check.
And all of this is built on some of the best magic I’ve ever read.
*Let us not forget the footnotes. Oh! the footnotes.
Robert E. Howard’s Conan the Barbarian series is a cornerstone of fantasy, & Conan himself is the biggest, baddest bastard in all fantasy.
I don’t have anything new to add, all my favorites have already been mentioned.
So instead I would like to take this opportunity to +1 some of those.
-Robert E. Howard’s Conan the Barbarian - The Original Sword and Socery stories? I would say that reading some Conan stories are essential to understanding any of the art that came about after the pulp age. So Conan should be required reading for an appreciation of most American art and literature. HP Lovecraft too, for similar reasons. Even if you don’t care for it, it’s influence casts a long shadow.
-Jonathan Strange and Mr. Norrell - Others have done justice to this book already. It’s big, but very good.
-Assassin’s Apprentice and the rest of them by Robin Hobb - Great easy writing style, and a fantastic plot and characters.
-Terry Pratchetts DiscWorld Series - All of them, any of them. Fun, funny, thought provoking. Really really good stuff.
-A Wizard of Earthsea - Just finished this after meaning to read it for years. It’s fantastic. Well deserving of its status as a classic.
-*The Dark is Rising *- Also fantastic. Another well deserved classic.
I am also currently working on a game based on The Malazan Book of the Fallen with another couple of SDMB members. I don’t know anything about the books, but from what I have learned working on the game I plan to bump them to the top of my reading list.
Oh and the Chronicles Prydain by Lloyd Alexander aren’t on this list anywhere! Get those too.
Seconded. I’ve been interested in urban arcana settings lately, and The Dresden Files is a great series. If you’ve seen the TV series, the books are noticeably different, but they’re a hell of a lot of fun.
The stumbling block for people, though, is the style of the novel. The florid language use and leisurely format cause a lot of people to bounce pretty hard off it.
And that reminds me of something I forgot to mention:
My suspicion is that for Christmas in 1979 somebody gave Gene Wolfe a Word-a-Day calendar and The Book of the New Sun is his elaborate revenge on that person. It’s still good but if you didn’t score 1500+ on verbal portion of your SAT be ready to look up a lot of words.
It’s only the fifth time that I’ve encountered gnomon being used, though admittedly I do not hang out with fanciers of that kind of thing.
With Pratchett I do not recommend starting off at the very beginning, like I did. He doesn’t truly pick up his stride until several books in. Or maybe I just don’t like Rincewind. Anyway, I recommend starting with Guards! Guards!, Small Gods, or Wyrd Sisters. And then everything else.
John Connolly’s The Book of Lost Things. A whimsical, disturbing, sad coming-of-age story.
He also tends to make things up for his world and never clearly explain just what they are until much later. There were a few things never clearly defined until the appendix of the last book. I know the books are supposed to be written by someone of that time/world and so they’d know what they are not not explain, but it still seems like poor writing to me.
Whaa? You’re kidding, right? RIGHT?
Okay, I guess YMMV, but I thought Mistborn was awesome upon awesome. Now Elantris, that was forgettable; I don’t understand why everyone seems to think it was so great.
Also, Mistborn is the only fantasy novel I can think of that features a likable eunich.
Also, there’s a list being written on the Barnes & Noble fantasy forum that might be helpful to you.
One of my favorites as well.
Another in the short fantasy section: Invisible Cities by Italo Calvino.
It’s a piece of land surrounded by water, right?
The Chronicles of Prydain: great recommendation. Definitely children’s lit, unlike Wizard of Earthsea, but if you can dig that, they’re great. (We’re talking Book of Three, Black Cauldron, etc.)
Typing that makes me think that when recommending series, it’d be helpful to provide at least the first title; otherwise, it could be a lot harder to find them at the library.
Daniel
That’s No Man. 
Erikson sets up a very interesting world, but I don’t think he writes dialogue that well, or has that many deep or complex characters (I’m up to book 3 so far, so hopefully it gets better later on). They all seem to be the same version of “grizzled bad-ass warrior/assassin/mage that does whatever they can to protect the innocent.” To make a comparison to ASOIAF, it feels like 90% of the major characters in Malazan are Qhorin Half-hand.
I also don’t really like how dragonball-z-ish most of the battles end up. There’s never really any sense of tension or danger, because even when the heroes are surrounded by dozens of warriors on all sides, they still manage to pull of a spell that obliterates everyone, or a demigod interferes and a giant boar hoof comes down and steps on the bad guys. More deus-ex machinas than you can count. I much prefer GRRM’s limited magic approach.
Darn. I was reading, and reading, and thought no one was going to mention Jonathan Strange and Mr. Norrell. Of course, right after that there’s a giant love-fest for it. 
I’m not a fantasy reader at all (I need to bookmark this thread and give some a try sometime) but I loved this book, which I think means it’s very accessible to non-fantasy types. Of course, I adore Jane Austen and Harry Potter with an unholy passion, and it was described by some reviewer as a mix between the two, so that might also be why. I recently gave it to a friend who loves fantasy, too, and I rarely give specific books as gifts.