When thinking of fantasy, the name "Robert Heinlein" is not one that immediately comes to mind. Heinlein made a name for himself as a science fiction writer, which is why it's difficult to know what to make of his 1963 novel, Glory Road. The novel had first appeared earlier the same year as a serial in The Magazine of Fantasy & Science Fiction and, as was once a common practice, particularly for genre fiction, it was collected together and published in a complete form.
Glory Road tells the tale of a veteran named Evelyn Gordon, who is spending some time on the French Riviera after having been discharged from the military after serving in an unnamed conflict in Southeast Asia (presumably Viet Nam, but this is never stated in the text). While there, he answers a newspaper advertisement that puts him in touch with a woman of -- literally as it turns out -- unearthly beauty named Star, who enlists his aid in a quest for a mysterious item known as the Egg of the Phoenix. Along with Rufo, an older man who acts as Star's assistant, Gordon and Star encounter a wide variety of dangers, from tricks and traps to minotaurs and dragons, in their quest for the Egg, an item whose true purpose and nature are very different than Gordon initially imagines and whose discovery opens up even wider vistas for him to explore.
As I noted, Glory Road is an odd book that doesn't sit comfortably within the science fiction genre for which Heinlein was well known. Neither is it a pure fantasy. Instead, it straddles both genres, borrowing liberally from each, which may explain why many modern Heinlein fans dislike it. For myself, I've long felt that Glory Road was Heinlein's attempt to produce a "sword-and-planet" novel after the fashion of Burroughs, but on a stronger science fiction. The result is a very uneven novel, but a fun one, provided you aren't distracted by the typically Heinleinian disgreesions into his then-evolving socio-political philosophy. The book thus has an odd feel overall. Some readers may see this oddity as contributing to their enjoyment, while others may see it as detracting from it. In either case, Glory Road is another book from an era before the boundaries between science fiction and fantasy were less well defined and even a writer as solidly in the former genre could freely borrow from the latter without too much comment.