If you want to avoid cliches, spend some time thinking about what story you want to tell. If you could sum up a story in a single theme (paranoia/adventure/corruption/anti-industrialism etc.), then you have a well focused story. If you can't, then your story lacks focus. Some epic stories have multiple themes (Lord of the Rings has all of those), but you should start small and work up to that sort of thing. When coming up with a theme, pick one that interests you in particular, which hasn't already been commonly touched upon, and is of personal relevance.
Once you have a single theme you want to write about, create the story and the setting around it. Don't just default to feudal-Europe, edo-period Japan or a steam-punk Victorian setting. Come up with a setting which best accommodates the theme of the story. If it is a story about self reliance, a harsh jungle or desert setting would be a good idea. If it is a story about deceit, an urban or court setting is sensible. Once you have a location, do something to it to make it unfamiliar of original. This isn't just for aesthetic purposes, it is for best making an intriguing world that reflects the message of the story.
When coming up with characters, grant them at least one characteristic which makes them unique. IT can be literally anything. Just so long as you don't treat a character as an object who provides exposition, or who the hero just has to kill at some point. Perhaps it is an evil enemy general, who has a soft spot for making models of stuff. Perhaps it is a doctor with suicidal tendencies. Practically anything can make them more human. It doesn't have to be kooky, but it can be. These things help avoid creating obvious strawmen or flat 2-d characters. Which aren't necessarily a bad thing, but can be boring if they're sort are already too familiar with the reader. We have already seen plenty of greedy industrialists/barons or sanctimonious, corrupt clerics. If you want to do something interesting, turn it around and make the court jester greedy or the herbologist as sanctimonious.
EDIT: Dry; nothing on it