Song of Fire and Ice can’t be beat for intricate, bloody, edge-of-your-seat plot. It’s not romantic in the ooey-gooey sense, but the friendships and loyalties between the various characters keep it all very interesting.
The Outlander series was way too goopy for my taste, but if you like romance, you’d probably dig it.
Don’t forget me and Cynthia!
Don’t forget me and Cynthia!
Damned preview ate my sig line!
Getting frustrated here, people!
To continue with Kay, the Sarantine Mosaic duology has a more conventional romance story–at least, moreso than his earlier works.
And romantic love is, IMO, central to the plot of A Song for Arbonne. (viz. Bertran de Tallaire and, uh, his lost love. Starts with an “A”. Dammit.)
If you want hot, steamy stuff, then I can’t help, but I can make a couple of PG/PG13 suggestions. First, try the Spellsinger series, by (I think) Alan Dean Foster. The main character does end up with a human girlfriend, but the girl he had a crush on runs off with a rabbit (in the Spellsinger world, most animals are approximately human in shape, size, and intellect).
And if you don’t mind a children’s series, try the Chronicles of Prydain (starts with The Book of Three), by Lloyd Alexander. Although there, the love story is most obvious when the princess isn’t present, and the hero is pining for her. Since they’re written for children, they go pretty quickly, and you can probably read all five in a few days.
You might also like Edgar Rice Burrough’s Mars stories (which are really more fantasy than SF), if you go for the idealized style. That is to say, the hero is always strong and brave, the princess is always beautiful and noble, and they both fall instantly in love on first sight and stay devoted to each other forever. The first in this series is A Princess of Mars.
Beat it! 
Well, what about Robb and …hmm, no. Or Littlefinger and…no, no, and eww…
(Actually, I would consider Sansa and the Hound’s relationship of a sorts to be kinda romantic. For what it is. Which isn’t much. Yet. Tyrion and Shae had, well, a lot of sex – maybe that counts?)
I second Alessan’s recommendation of Stephen Donaldson’s Mordant’s Need books – great plot, great world, great characters, and a remarkably sweet love story that’s not trite or cloying.
I’ve always found the strength of the love between Fitz and Molly in the Assassin series by Robin Hobb to be quite touching.
Sharon Shinn writes books that are basically traditional romances disguised as science fiction/fantasy. They’re pretty good, though a bit overly sappy at time. The only strictly fantasy book of hers I can think of is “Summers at Castle Auburn,” which is sweet, but not one of her best. Her Archangel series is one of those books, like Anne McCaffrey’s Pern series (hey, those have romance too) which span the boundaries between science fiction and fantasy, but the first books, in particular have a very fantasy feel. I think her best effort is “Heart of Gold,” which is kind of science fiction, but definitely not hard SF.
Emma Bull’s “War of the Oaks” has a lovely romance that always makes me feel all warm and fuzzy inside, but that’s not a series either… sorry. I don’t like most series much, actually.
Kids series with nice fuzzy romances:
the Enchanted series chronicles by Patricia Wrede (especially 2 & 4)
the Dalemark chronicles by Diana Wynne Jones (especially 4)
It takes a while to get to the romance in both of those, but they’re still better than a lot of modern fantasy.
I can’t believe no ones thrown Katherine Kerr’s Deverry series into the pile! A Searing love tale across several incarnations 
And a cracking good plot too.
IMHO the first four are the best
ie Daggerspell, Darkspell, Dawnspell & Dragonspell (they have different names in the US, I think Dawnspell = The Bristling Wood & Dragonspell = The Dragon Revenant)
The follow up series starts well but gets more and more ‘fantastic’. I still like em, but they are not as good as the first 4 in my opinion
Not a series, but Patricia McKillip’s The Forgotten Beast of Eld is one of the greatest romances written in any genre.
And I back-up Chronus for both the Chronicles of Prydain and Edgar Rice Burrough’s Mars stories–I was thinking of both.
Finally, Nancy Springer wrote of series of books, some more loosely connected than others, and they is romance, but I can’t remember which books have which love story. Some titles are: The White Hart; The Silver Sun; The Sable Moon and* The Black Beast*. I suspect the first tow have the most conventional love stories.
I’m going to repeat the recommendation for all things Melanie Rawn in this topic – good, strong plotlines and well-developed characters, and even even romance. Though I’d have to say it’s not the “soppy twaddle” GuanoLad characterized it as, it’s also not your standard “swords and sorcery” fantasy stories. Rawn focuses much more on characters than events, and while the stories are strong in general, it’s the characters that you come away having the strongest affinity for.
The Dragon Prince and Dragon Star series were her first, and while Dragon Prince is the better of the two, neither is as good as her more recent (and unfinished, curse it) series, Exiles. Two books of three are out, and they are excellent. Highly recommended, if only she would get that third book out!
If you haven’t already read The Mists of Avalon, run, don’t walk. And of course LotR… If you don’t mind YA Lit, you could read His Dark Materials by Philip Pullman.
Try “The Stone Dance of the Chameleon” series by Ricardo Pinto. I’ve only read The Chosen, but it was wonderful, very complex, with a gay (or perhaps bisexual, the issue hasn’t been fully explored) hero.
Julie
The Nightrunner Series, by Lynn Flewelling, also centers around two gay characters and their relationship. The first book is Luck in the Shadows, second is Stalking Darkness, third is Traitor’s moon, supposedly with more on the way. Not a literary masterpiece, but it does have some humor and some good action scenes.
FANTASY, QtM? I’ve heard that story called a lot of things, but not fantasy.
I second Kallessa’s recommendation of McKillip’s Forgotten Beasts of Eld (both as a love story and of just a wonderful story).
In addition McKillip’s Riddlemaster trilogy (Riddle-Master of Hed, Heir of Sea and Fire, Harpist in the Wind) has a central love story that is moving, although it is not played out with much “romance.”
I also second Donaldson’s Mordant’s Need, (Mirror of Her Dreams and A Man Rides Through) for the same reasons that Alessan gave.
And, of course, Robin McKinley’s retelling of Beauty (and the beast) is great on several levels.
I’m a huge fan of Barbara Hambly.
Probably my favorite of her fantasy series is the Darwath trilogy, though now it’s five books because of the two series. The Time of the Dark, The Walls of Air, and The Armies of Daylight are the original trilogy. There’s a smidgen of romance, very well handled and understated. She picks up the characters several years later with Mother of Winter and then Icefalcon’s Quest.
Second favorite trilogy - though it’s really more a two-parter with a sequal and a fourth book set in the same world but different characters - is the Darkmage series. Again, romance, and again, understated and very well handled. One of the things I really like about Barbara Hambly is her ability to write both male and female characters in a very balanced way. They are believeable, whole people, and they don’t do stupid stuff just to advance the plot. That makes me very happy.
May I recommend the Sword In Exile series by Ann Marston?
Book 1 - Cloudbearer’s Shadow
Book 2 - King of Shadows
Book 3 - Sword and Shadow
A phenomenal series, loosly based on Celtic myths. Lots of “romance”, but won’t cut it if you’re actually looking for graphic descriptions.