Here are some other fantasy stories with strong (mostly female) characters (some with a little romance) that I think you will like:
Stardust by Neil Gaiman.
The story of young Tristran Thorn and his adventures in the land of Faerie. He has fallen in love with beautiful Victoria Forester and in order to win her hand, he must retrieve a fallen star and deliver it to her.
Sabriel by Garth Nix.
Sabriel, daughter of the necromancer Abhorsen, must journey into the mysterious and magical Old Kingdom to rescue her father from the Land of the Dead.
The Princess and the Hound by Mette Ivie Harrison.
George has always felt burdened by his princely duties, and even more by the need to hide the magic through which he speaks with animals, but when he is betrothed to the strange princess of a neighboring kingdom, his secret, and the persecution of people like himself, must come to an end.
Princess Ben by Catherine Gilbert Murdock.
A girl is transformed, through instruction in life at court, determination, and magic, from sullen, pudgy, graceless Ben into Crown Princess Benevolence, a fit ruler of the kindgom of Montagne as it faces war with neighboring Drachensbett.
A Curse as Dark as Gold by Elizabeth Bunce.
Upon the death of her father, seventeen-year-old Charlotte struggles to keep the family's woolen mill running in the face of an overwhelming mortgage and what the local villagers believe is a curse, but when a man capable of spinning straw into gold appears on the scene she must decide if his help is worth the price.
Chalice by Robin McKinley.
A beekeeper by trade, Mirasol's life changes completely when she is named the new Chalice, the most important advisor to the new Master, a former priest of fire.