I’ve read a lot of very conventional fantasy (conventional both in the sense that it follows fantasy tropes and stereotypes, and in the sense that it doesn’t push its own original concepts far enough). There are a lot of good medieval fantasies, historical fantasies, and alternate Earth fantasies; my two favorite authors, Kay and Martin, write in those genres. But at the same time, fantasy has such limitless potential that I don’t think every new author needs to follow in that vein.

1) Remove something that Earth’s humans have always had to deal with.

What happens if you really do have a society with equal gender roles, where things have always been that way, or a different gender setup altogether? What develops should be wildly different from the way that Earth-like fantasies handle things. Living arrangements should be different: marriage, the raising of children, the consideration of love as opposed to money and power. Attitudes towards sexuality could be more relaxed, or strict, but in different ways. (Perhaps it’s childbearing or child-siring that’s considered the true sign of a marriage, so the mere sexual act has no importance at all, but getting pregnant or getting someone pregnant changes things). Clothes themselves will be different, as there wouldn’t be much reason for women to wear gowns that would restrict their movements and keep them walking in a delicate, lady-like fashion.
Or alter a fundamental fact of natural existence. What happens if diseases are missing or rare? (Actually, in lots of fantasies they are, but that’s author carelessness, not design). There goes one enormous, uncontrollable, unpredictable factor that was likely to come along and destroy medieval villages when they least expected it. What if the weather has always been magically controllable? What if people tend to remain healthy and able to move around easily as they age? What if accidents are nonexistent because of the presence of numerous fortune-tellers whose words prevent them? Lots and lots of Earth’s problems could be removed in a fantasy, to birth changes and new problems in their wake.
That’s the point, of course. Altering a problem to produce Paradise will make a boringly perfect place, and it’s hard to write about one of those convincingly—and by this point, the seemingly “perfect” society that has something rotten in the state of Utopia has become a cliché of its own. If you make a gender set-up different from the norm, take into consideration the problems too.

2) Introduce something that Earth’s humans have never had to deal with.

Very, very easy to do in a fantasy, but oh so rarely followed up on.
There’s a reason that a lot of medieval fantasies don’t work for me, and it’s because the author adopts features of the medieval setting willy-nilly and then combines them with fantasy features that should negate them. Probably my favorite example is dragons and castles. So you have a world where there are dragons flying around all over the place, and they’re aggressive and want to hunt humans, and then the humans build a castle.
Can you think of an easier place for a dragon to attack? Their wings will carry them over the walls. Their tails could knock down the walls fairly easily (and trap anyone who’s not outside under the rubble). Their horns can gore people running about the courtyard in a panic. They might not be able to fit their whole bodies into little secret passages, but if they can get their snouts in, one quick blast of fire will roast those pesky royal heirs. Weapons generally bounce off their scales. A flying dragon’s wings might be vulnerable, but a dragon who’s intelligent, which is the majority of them in fantasies these days, would probably come up with some way to defend against that. And if they have magic, they might be able to hover off in the distance and level the castle that way.
Basically, castles are sitting targets. Yet fantasy authors merrily scatter them over the landscape, and never think of having their dragons attack them.
Magic is another thing. It would make sense, if it is a natural feature in the world, not to have it be all tame and polite and pink-unicorn-ish. How many Earthly natural forces are like that? Weather’s not. Earthquakes aren’t. Landslides and forest fires don’t ask humans’ permission before they happen. Droughts and plagues and famines and mental illnesses and crash-landing meteorites are powerful things that take human ingenuity to survive, not someone waving a hand and saying, “Do this. Do that.”
I would like to see more bad, nasty, wild, uncontrollable, chaotic, crippling magic. There’s often an undercurrent of fear about magic in fantasy novels, but the people who fear it often fall into one of two types: uneducated bumpkins, or people who want to persecute the Speshul group of magic-users and make them vanish from the world, usually for reasons that the author doesn’t even bother to make slightly plausible. Magic itself is either pink-unicorn-ish or supposedly “uncontrollable” forces that the hero manages to control in the end, just in time to save the day. (This is a common culprit in the deus ex machina ending). Where is the magic that scares the shit out of everybody?
Fantasy has literally unlimited possibility for dropping people into situations they’ve never faced in our history. I don’t know why so many authors are content to go with the simplest solution.

3) Remove the evil.

Fantasy authors can do a lot with moral universes. Unfortunately, a lot of them choose to play in moralistic universes instead, and tromp along Trope Road in doing so.
Even if you have a villain who is clever enough to outwit the hero a few times and has complex motivations, most fantasies still are a dash to the finish line for the hero. The villain has to lose, because he is the villain. There is a dark force threatening the world, and it must be stopped. No compromise is possible. There are sticky ethical situations at times, but they’re only minor ones; the hero doesn’t go through a crisis of faith as far as confronting the dark force because, after all, it’s dark. Everybody knows where they stand, and there are easy solutions in a time of crisis. Everybody knows exactly who to blame.
With the very best fantasies of this kind, I can do what I call “suspension of disbelief as to suspense.” Even though I know what the ending’s going to be—hero triumphant even if he dies, villain defeated, redeemed, or dead—I can pretend I don’t, and there are often enough twists along the way to keep me satisfied.
With the poor ones, there is no suspense at all. I’m expected to accept only fairy tale premises of good and evil. Well, while modern fantasy has fairy tales in its heritage, it is a very different genre (different even from the retold fairy tale), and I resent being told that I can’t question why the hero is the hero and why he’s doing what he’s doing any more than I can question why Sleeping Beauty is the heroine of her story.
Take away the ethical clarity, and you have whole new dimensions for fantasy to explore in. Perhaps magic is controllable, but it also causes horrible side-effects, like schizophrenia, for its users. Yet at the same time, it’s also enormously useful, easing other people’s lives in, say, the same way that electricity eases ours. Should the mages stop using their magic to save their own lives, when the cost of taking it away would be hardship, and perhaps death, for other people? Yet is the sacrifice the mages are expected to make fair, either?
Tell me who’s to blame in that one. Almost assuredly, different characters will have different ideas.
I’ve heard people argue that fantasy can’t be fantasy without ethical clarity, to which I say: Pffft. It might not be able to be high fantasy, or religious fantasy, or the latest Tolkien knock-off, but it can sure as hell be fantasy, a new subgenre maybe. And the people who whine about this often have no idea what they’re talking about. A Song of Ice and Fire is very, very medieval and history-based, but each character is the hero of his or her own life, and ethically muddy situations are everywhere. I think the people complaining about lack of ethical clarity have limited ideas of what fantasy can be.

4) Take away the humans.

There are many stupid little subgenres of fantasy I detest with an utter passion, but there’s a special black place in my heart for the fantasy where humans are the dominant species in the world just Because, and other races and magic are fading just Because. (The other races, by the way, comes off like absolute wimps most of the time, unwilling to take the simplest of steps to preserve their own lives).
Why do humans have to be the dominant species in a world? Why do they have to triumph over the other races in ways that the author never adequately explains?
Why do there have to be humans at all?
Yes, setting a fantasy in a non-human or partly-human society is hard, complex, and an uphill slog against many fantasy readers’ comfort zones. Good. Writing good fantasy shouldn’t be any easier than writing good science fiction, or good literary fiction, or a good essay. Let your imagination stop with humans, and perhaps spin in a few fading elves and dwarves whose only noteworthy characteristics are their height and their mining, and I think you deserve to be challenged.
If you’re still resistant to the idea, think about it like this: Many fantasy authors are fascinated by the idea of constructing their own mythology, languages, societies, or whatever their particular point of interest in their world is. (See point 5). Creating a world where humans have shared, very little, or no influence at all is an extension of that, not something so impossible that you should throw up your hands in despair. And it has the advantage of immediately forcing you to abandon a lot of the assumptions that conventional fantasies make, something that doesn’t always happen with mythologies, languages, and human societies. Assumptions about the most basic concerns, like fear of death or hunger, will alter if you have a race whose every individual knows from the moment they’re born when they’re going to die, or which feeds on sunlight and air. And that, I’m firmly convinced, is good.

5) Invest your fantasy with passion.

I often get the feeling with conventional fantasies that the author has no real interest in this world as a world, or these people as characters, or, in the worst cases, fantasy as fantasy. They bang out a few thousand pages about castles and kings and prophecies because it’s the thing to do. It’s no wonder they wind up with works that sit firmly in the stereotypes.
Go out and find something you’re passionate about (well, hopefully it won’t be that much of a search). Then put it in the fantasy. Better yet, if you’re just starting with a new world, create that world around the passion.
It is possible to love dragons with a great and searing love, and to want to write about them. But in that case, I would expect the fantasy to be full of that love, not dumping the limp stereotypical dragons on the page. I would expect to see dragons just about lunging off the page. Even if the human characters look dreary next to them, at least the whole book won’t resemble a stick drawing.
Tolkien didn’t write Lord of the Rings as a statement about gender, or to irritate people. He loved the Germanic mythologies, so they got incorporated into the work, and he created Middle-earth as “a world in which a form of language agreeable to my personal aesthetic might seem real,” to quote his letters. (There is a great article here that explains in loving detail how important the languages are to Middle-earth). Similarly, Ursula K. LeGuin did write The Left Hand of Darkness to see what would happen if she played around with a different gender situation, but she is interested in gender. Attempting to tackle a theme that you’re not interested in, or just because you think fantasies “have” to have certain tropes, will make your story a dull thing. If you write a book with passion, you might not create a work that appeals to everyone, but I’ll bet you dragons to castles it will appeal to more people than Cliché-world.
Leave out the kitchen sink, put in the passion.
I get impatient, sometimes, thinking of all the great fantasies that could be out there, and which I’ll never get to read if people keep treading these well-worn paths.