I have devoured two fantasy novels in the last month with very similar shapes: The Wheel of the Infinite by Martha Wells, and Paladin's Strength by T. Kingfisher.
They're both very good, but I liked The Wheel of the Infinite a lot better. In part because it's set in a world I'd want to live in; and in part because the romantic leads get to be well-adjusted enough to admit they're attracted to each other, and to get around to sex *before* they face mortal peril together.