Shards of Honor is a good start.
But it is part of a long series (The Vorkosigan saga) that meets meet the specs in pretty much each volume. Although the main protagonist of the first two--Shards of Honor & Barrayar; available at Baen as a combined edition as Cordelia's Honor--is female. A latter arc in the series--Memory, Komarr & A Civil Campaign; the last two available as a combo entitled Miles in Love--feature romance a bit more prominently as a theme rather than just a story element, along with the mystery and sf elements.
The most recent in the series, Captain's Vorpatril's Alliance is mostly a standalone and, again, romance is a central theme along with the action and the caper aspects.
If you're flexible in your definition of SF, several of Marion Zimmer Bradley's Darkover Novels fit the specs: The Spell Sword (with a general SF "fairy tale" plot) and its sequel, The Forbidden Tower (where "happily ever after" runs headlong in a stone wall of relative and culture-clash.
) both fit the bill.
Heinlein's Beyond this Horizon and Glory Road both run similar approaches; action, adventure, boy meets girl, boy wins girl...and what comes next? What *do* you do after you save the day and get the girl?
Poul Anderson's Tau Zero is hard SF with an enormous scope wrapped around a cross-cultural romance story.
James P. Hogan's Thrice upon a Time is a very good story of time travel and love in a time of cataclysm.
And if oddball humor and capers fits your interest, Harry Harrison's The Stainless Steel Rat finds the protagonist, Slippery Jim DiGriz, wooing Angelique the sociopathic killer of his dreams as she tries to seduce him back to a life of (unrestrained) crime.
Also on the oddball side, and likely hard to find: Donald Barr's Space Relations.
For starters it is a character-driven space (soap) opera that works. The core of the story is the romance of the two protagonists but it is hardly a fairy tale romance.
http://www.goodreads.com/book/show/2...pace-relations
It also has a few things to say about power and slavery and human nature. Not for everybody but those that like it seem to really like it.