I didn't go threw the whole topic so some of these may already have been mentioned, but here's some fantasy novels you may not have heard of.
The Runelords - fantastic and original fantasy series, especially the first four. Definitely worth a read if you're looking for a departure from the old "elves, dwarfs, wizards and dragons" staple.
Terry Brook's books - the Shannara series by Terry Brooks is pretty standard (though very good) fantasy affair, but his "Word & Void" trillogy is terrific modern fantasy, and his "Genesis of Shannara" trilogy is downright amazing post-apocalyptic goodness, though it requires reading the the rest of his books to fully appreciate. His "Landover" series is a totally different style than the others, and is great if you want a much lighter and modern read.
The Sword of Truth - Not as good as the aforementioned series, but it has its moments.
The Wheel of Time - Ok, this might be breaching the whole "dedicated fanbase" clause, but this series is pretty much king of Fantasy. Original, complex, and incredibly deep and engrossing, this series is only for the most dedicated fantasy lovers. The only problem is that Robert Jordan, the author of this incredible series, died before he could finish his epic. Thankfully, the author they got to finish it for him (using Jordan's thankfully detailed notes) is so far doing an admirable job of it.