Just because we've heard an idea before doesn't mean it can't be done in a novel way. But what can we do to make sure that the story we have is unique, and not like others of its type?
A lot of the stories we're familiar with come with a set of underlying assumptions about their execution. Settings in which they're expected to take place. Characteristics that their characters are supposed to have. Ways their cultures are supposed to work. Technologies that are supposed to go together.
There's no real reason why these things have to be maintained as they are. Pick one and change it - not a little, but in a way that will make your story utterly different, so you'll really have to sit back and THINK: wow, how far do the consequences of that change really go? Here are some ways to try.
- Set the fantasy story in a technological setting. Steampunk did this, and look what happened!
- Take an expected technology away. I rarely see this done, but I'm doing it myself: Varin has no visual tech, for cultural reasons (no movies, computer monitors, etc. and a sense that even photography is inappropriate). And what if you did something really radical? Took away fire? Or the wheel? What would happen then?
- Change gender roles. Reverse them, okay sure, but what if you altered them? Ursula K. LeGuin did that by taking away gender in her own way, and bang! You could even have gender roles look one way in one part of your society, and totally different in another part, so long as there are solid cultural reasons behind it.
- Change diet. And don't stop with what's on the table, but contemplate the consequences for agriculture, for lifestyle organization, for food culture and values.
- Change character. I usually do this by changing culture, because that then changes the fundamental way that a character thinks - changing the metaphors they use to describe the world, and changing the rationale behind the decisions they make. You want readers not to be able to predict what your character will do? Alter their cultural morality and see what happens!
But that's the whole point.
If you can make a twist, and explore its consequences on a larger scale while maintaining the internal consistency of your world and its cultures, believe me, you'll have something different.
It's well worth thinking about.