Some clarification probably required: I don't consider Tolkien my favorite fantasy writer. (That would be Guy Gavriel Kay). I do think that he built a very complete world, and I wish more fantasy authors had the time and dedication that he did, and were as judicious about their use of mythology and as in love with their chosen subjects. I don't think his characterization is the best in fantasy, and his descriptive prose can go a bit long.
But he is not to blame for the way that people have taken his books as the model for fantasy. His own writing on the subject of fantasy recommends mining the past for useful story-writing tools, not taking the pattern that someone offers you unaltered.
And most of the time, those imitations are themselves imperfect, and ignore a lot of what went on in the beginning story.
1) Tolkien's world isn't actually medieval. The only society that might qualify for this is Gondor, which does have a King at some points in its history and which calls on its allies, lesser lords, to help defend it in war. But Gondor is ruled by a Steward at the time of the War of the Ring, something a lot of people seem to miss. Most fantasy societies find this intolerable. In fact, they find anything other than a right and proper blood King on the throne intolerable. They take Aragorn's quest for the throne and idealize it into something that it never was.
Don't make your monarchy slavishly obedient to that fantasy idea. For one thing, fantasy monarchies are very rarely like medieval monarchies, with their complex dealings between monarch and nobles, the laws of vassaldom, serfdom, and the justifications for kings taking the throne, such as the divine right rule. Instead, the aspiring fantasy writer creates a hero who gets along with everybody as well as Aragorn does with most people and has been separated from his throne in the way that Aragorn was, and send him after it. No mention of the time that it took Aragorn to get the throne back, or the antagonistic way that Denethor and Boromir reacted to the idea, or even that Aragorn didn't just march into Minas Tirith; he came in under cover of night to heal people first. Fantasy Tolkien-clichéd heroes sacrifice what makes Aragorn an imperfect fantasy monarch for the sake of not doing any work.
Give your King some problems. Show that the people who oppose him, though they may be wrong, are not all blind and willful idiots. Give him qualities that would make him a good monarch even if he wasn't of the right blood.
2) The Dark Lord is just dark. The characterization of Sauron in LOTR is somewhat lacking, of course. We don't see much of the complex process by which Sauron became a servant of the greater evil, Morgoth, and it's all too easy to forget the, "Nothing was evil in the beginning. Even Sauron was not so," line. Additionally, the movies have given a picture of Sauron as exclusively evil and threatening, so characterization goes even further out the window.
But one more fantasy dark lord who wants to take over the world Because, and moreover has some fortress or mountain somewhere from which he rules, and I will scream.
It's always possible to make the evil guy more complex. If you want another example of a paradigm where complexity gets ignored but doesn't have to be, look at Christian mythology. Satan falls because he rebelled. Most people see that as inherently wrong, and don't bother probing further. But probe further, and you get into sticky questions like: If God could foresee the revolt of the angels, why didn't he prevent it? If angels, unlike humans, had no free will, then doesn't that mean that the revolt was destined, and Satan was only doing what he was supposed to do? And then there's the tricky little idea that Lucifer was the best of the angels before he fell; "Lucifer" means "bearer of the light."
Start asking questions of your own dark lord and see if he can't answer them in a more complex way than you've been giving him a chance to so far. And don't leave him locked up in a fortress all the time, either, or at least give him strong minions if you do. Sauron had his Nazgûl. Most fantasy Dark Lords have cheap knockoffs.
3) There doesn't have to be a typical Quest Object. As Tolkien's characters themselves note, the Ring is a rather odd Quest Object. The journey in LOTR isn't actually about finding the Ring, but returning it to the place it came from and destroying it. The fantasy Quests that spring from bastardized versions of Tolkien ignore this, however. The Quest Object is just about always beneficent (in fact, some of them can't be used by evil guys at all) and far away, so that the point is getting there and using it. The idea of destroying it even if it's dangerous rarely, if ever, occurs to your typical fantasy
I'm of the firm opinion that you don't need a Quest Object at all, or that the Quest doesn't need to exist, but if you're going to use it, please don't send your hero after the usual sword or amulet or jewel. Or consider what unexpected side-effects it might have. The Ring didn't have a whole lot of signs that it would possess people, after all. The writing that explained what it was would probably only become visible if one knew all about the Ring in the first place. And Tolkien represented very realistically the process of ignoring and forgetting that happened when the Ring was lost. Few Quest Objects get the same treatment. They seem to have been remembered perfectly and reverently throughout the Ages.
Make the sages wrong, for once.
4) The wildly disparate band of people going on the Quest is not what actually happened in Tolkien. Everyone in the Fellowship has a reason for being there- choosing to go along (Frodo, Merry, Pippin, Sam), representing their race (Gimli, Legolas), or being aided along their own Quest (Aragorn, Gandalf, Boromir). There are no random people added to the pile as obvious foils for the hero, comic relief, Token Character of This or That Persuasion, etc. The closest token characters are Gimli and Legolas, and their inclusion is a political decision, not authorial whim.
They also manage to function fairly well together, in spite of some snapping and debates. I always wondered how some of those groups that consist of a fussy princess, a taciturn guardsman, a flighty mage, a calm priestess, and the token dwarf or elf character actually got along. Their personalities clash, and a lot of them have, "Oh, well, I'm just going along with you because I want to!" reasons.
Fantasy groups in general should be better-designed, and when the danger gets tough, the hero or heroine's going to need people who really have reasons to be there. What's to prevent them from saying, "See you?" and fleeing otherwise?
5) Tolkien wasn't binding anyone to a particular set of races. At the time he wrote, elves were mostly ignored in fantasy, or appeared as cute little fairy creatures like Santa's elves. Tolkien chose the name- though he admitted to being unhappy with it- and transformed the ones who bore it into different creatures entirely. He gave them histories and languages, a reason for leaving the world to humans, and a complex otherness. It's not his fault that a lot of fantasy authors have decided they absolutely must have elves in their stories, and must make them tall and beautiful and weepy, without inventing any of Tolkien's reasons for it.
Dwarves are a similar case. Tolkien mined Norse mythology, especially the Eddas, for his dwarves. Other fantasy authors have mined Tolkien. If it's too much trouble to go back to the original mythology, they could at least have invented their own set of characteristics, but instead they adopt beards for everyone, being good at metalwork, being greedy, and even the enmity between elves and dwarves and the slower fertility of the dwarven race without blinking. Tolkien had the "Why?" of those firmly in place (dwarves were created in a different way than Elves, and caused quite a lot of slaughter in the First Age among Elves, as well as having minor spats with Elves throughout other Ages; and only about a third of dwarves born were women, who often didn't marry). Other fantasy authors rip out the "What?" without looking into their own "Why?" and plant the concepts in their own worlds, never noticing their pathetic dangling guts.
Orcs and hobbits are almost entirely Tolkien's invention. Other fantasy writers took them, sometimes slapping other names like "halfling" on them, and then blamed Tolkien for being so clichéd, which is exactly the wrong way round.
6) Tolkien's hero was average, and needed help, and failed. This is the place where most fantasy authors, who love to simultaneously call themselves Tolkien's heirs and blame him for a lot of what's wrong with modern fantasy, err the worst. It's hard to look at Frodo and see him as someone extra-special. The hints in the books that a higher power did choose him are so quiet as to be unnoticeable. And he wouldn't have made it as far as he did without his companions. And he doesn't keep from falling into temptation.
A lot of modern fantasy heroes are completely opposite from this. They start out extraordinary, and they stay that way. Other characters are there to train them, or be shallow antagonists and love interests and worshippers, not actually help them. And they don't fail. (Damn it, I want to see more corrupted fantasy heroes.) It's not fair to blame Tolkien for the disease that fantasy writers have inflicted on themselves. Sleeping with your own misconceptions and hero-worship will give you interesting venereal diseases like that if you don't use protection.
Fantasy could use more ordinary people who are afraid and don't know what the hell they're doing, but volunteer for the Quest anyway.
It's misinterpretation of Tolkien that's the problem, not Tolkien himself.