The following recommendations aren't necessarily my favourite books - it's more books I recall enjoying, but which are currently not tremendously well-known. You can take recommendations for the more well-known stuff (like McKinley's Beauty) as assumed.
The Daughter of Time - Josephine TeyI'll start with the only book which, when I'd finished reading it, had made the world a different place. The ground had shifted.
The Daughter of Time has one of the most unutterably boring premises I've ever encountered. Tey's British police detective is laid up in hospital, restless, and his friends and acquaintances bring him history books to distract him. He reads a bunch of books about Richard III. The end.
This is a book not simply about Richard III, but about the construction of history. About all the things we think are real, known and accepted fact, without really understanding how facts are constructed. I would never have believed I could be so fascinated by this book - enough that I've re-read it a number of times.
Black Hearts in Battersea - Joan AikenBlack Hearts is the second book in Aiken's "Wolves" series, but the first, the somewhat saccharine Wolves of Willoughby Chase, can be safely skipped over. Black Hearts introduces one of the stand-out absolute best YA/MG girl characters in all of literature - Dido Twite.
Dido's world, an alternate history with a distinctly Dickensian feel, is dark and unpleasant, and Dido is at the absolute bottom of the heap. Defiant, mouthy, indomitable Dido Twite, who looks like a molting sparrow and is the bravest person you'll ever meet.
Myth Happens'Myth Happens' is my own term for a sub-genre of MG-YA books set in this world, where creatures of magic and myth take over the lives of a group of children - often taking them off to other worlds. If you've read the The Dark is Rising series you'll have met this concept before.
The Weirdstone of Brisingamen, The Moon of Gomrath, The Owl Service - Alan GarnerThe magic in Alan Garner's books is dark and strange, sometimes creepy, often overwhelming, at times quietly invasive. Haunting.
The Weirdstone of Brisingamen and The Moon of Gomrath are the first two parts of a trilogy written in the 1960s. Garner has finally completed book three - FIFTY YEARS LATER! And George R R Martin fans thought they had it hard.
The Owl Service is not part of the same series, but is definitely a book which will stay in your head a long time after.
Speak Daggers to Her - Rosemary EdghillBack when urban fantasy and paranormal romance weren't formalised genres, Rosemary Edghill (a pen name of eluki bes shahar) was writing the Bast series. Bast is a practicing white witch: a pragmatic woman dealing with the tensions of the neo-pagan community.
This is not a series with vampires and werewolves around every corner, nor is there hot sex at every opportunity. Bast finds herself in the role of detective, and her investigations are the focus of the story.
A fascinating look at neo-pagans, thoroughly enjoyable 'teckery, and some rather dark developments at the end of the series. One of the few urban fantasies I found at all interesting.
Secondary World Fantasy
Angel with the Sword - C J CherryhA secondary world version of Venice, with one of the romance tropes I'm a complete sucker for - determined, defensive, independent lower class woman saves upper class pretty boy.
While not one of Cherryh's better-known books, this is my favourite of her work. It's a stand-alone, set in the shared world of Merovingen, and just, hell, if you like romance, and really solid world building, and saving pretty noblemen from drowning, you'll be all over this book.
Point of Hopes - Melissa Scott & Lisa A BarnettAnd now a secondary world version of Reformation/Renaissance times!
Point of Hopes is one of the few books I've encountered which, like Champion of the Rose, is set in a bi-normative world. Nicolas Rathe, a 'pointsman' (guard/policeman) is trying to work out why so many children are disappearing, and teams up with Philip Eslingen to investigate (leading to a nice little romance).
The worldbuilding in this book and its sequel is outstanding, astonishingly intricate, never overwhelming. Tremendous.
Song of Sorcery - Elizabeth ScarboroughFluffy fantasy!
Light-hearted, fairy-tale-ish, dramatic, romantic. Great for younger teens or those who want something sweet and light.
First in a series of related books which are straight-out fluffy fun.
The Universe Against Her - James H SchmitzFirst in a series of books about Telzey Amberdon, one of the first kick-ass teen heroines. Telzey is a xenotelepath, and the government doesn't like her much. But there are giant psychic cats! What more could you want?
By today's YA standards, this is fairly mild - Telzey is a young lady with little apparent interest in romance. But lots of espionage and sneaking about and giant psychic cats!
As an added bonus, I believe the entire series is available for free at Baen's Free Library.
Hellflower - eluki bes shahar
The Price of the Stars - Debra Doyle and James D MacDonaldSmugglers! Pirates! (Oh, sorry, 'freebooters'.) Two classic space opera series.
If you were going to pick just one, go for Hellflower (Butterfly St Cyr and Tiggy Stardust! Seriously!), but both are great reads.