I just finished reading _The Bear and the Nightingale_, by Katherine Arden, and it has a very similar feel to Robin McKinley's fairy tale retellings. However, this story doesn't revolve around a HEA romantic relationship (though every single character in this book tries to convince Vasilisa she wants to marry).
That said, my mind kept insisting that Konstantin was really Judge Claude Frollo from Disney's _The Hunchback of Notre Dame_.