Celia S. Friedman's Coldfire Trilogy is a rather dark but brilliant series about a planet (which I guess technically makes it sci-fi, but in practice it's fantasy) dominated by the "fae", the local magic that is found everywhere in nature, but particularly in places where forces of nature are very strong, like oceans or volcanoes. Since "fae" and technology don't coexist very well, the society has quickly regressed to a medieval one, and one of the main characters is a kind of warrior-priest, or a member of a knight order if you will, who is also trained in the use of the magic flows. It's the other protagonist who is most remarkable, though, as he is rather evil by any standard, and one of the best anti-heroes in fantasy.

And then there's Marion Zimmer Bradley's "Mists of Avalon". There are probably dozens of retellings of the Arthurian myths, many of them semi-fantasy, and I guess we all have our favourites; that one is mine. It's rather feminist, at times militantly so, which puts some people off. There are a number of prequels, but I don't like them that much.