Lots of awesome answers so far. An important thing to realize is that tropes and cliches can have a place in a storyline. Most of the time, the "save the princess" routine will end up the same way. Sometimes, your party gets to the princess, she didn't expect you to get this far and is actually blackmailing her parents, and then tries to kill you all with surprising expertise. The point shouldn't be to avoid all cliche, moreover it makes for a more fun time if the players are always guessing. They may be right a majority of the time, which is fine, but that doesn't change independent variables. If they are too comfy in cliches, they might feel like things are getting stale and they might be able to predict the storyline too easily. Other players may actually find comfort in some consistency. In either case, it doesn't hurt to allow some cliche but then throw them a curve ball at DM whim.
Having said all that, one thing I like to do when I the pace is too fast for me to improvise quality characters and situations: Auto-generate characters using resources such as mentioned in other answers. Then roll a dice to pick one stat and one skill. I make this that character's most obvious nature and driving passion, even if that isn't their best randomly-generated stat or even if they effeectively have subpar ability in it.
This is Dungeon World's method; pick a motive and a "knack" (a skill
or background), and figure out how they can use the latter to pursue
the former. It's a very quick way to breathe life into a character, so
much life in fact that it can significantly alter the direction of the
adventure. – @SevenSidedDie
Example: My adventurers decided to unexpectedly run about town to send all the townspeople through the Spanish Inquisition. I had not prepared this many NPCs. I resorted to my method by calling a smoke break for our smokers, I quickly generated a couple dozen characters, used random number generators at random.org to get big lists of custom random numbers, highlighted each focal stat/skill, and I was good to go. After the first smoke break, they ran into a magic shop. The shopkeeper's assistant, their first victim of rapport, turned out to be a half-elf with really poor hygiene who was interested in diplomacy. Quick check at his other stats and I realize he's a perfect match for a foolish know-it-all that isn't aware he smells bad and is really bad at diplomacy. He started with horrible customer service, then starts gossiping about town politics. Answers the party's questions, but also interjects with "hey, I got this problem.. I think I can get the town to do away with that stupid water well and replace it with a nice chicken fighting arena. I was thinking if I send you guys along with these pastries as a gift, we can persuade them." Box of pastries is messy, nasty and smells horrible, no pay-off for players to run errands for idiot magic shop assistant. We had a number of run-ins similar to this, some almost comical and some just interesting (graceful-like-a-cat rogue extremely interested in becoming a master bookbinder). Some had no pay-off if the party spent time with them or ran errands, some wouldn't even talk to the party, a few had pay-off that wasn't related to their quest, and I had my phone set to vibrate on silent at a certain time to let me know that the next townsperson would have clues about the quest. We had a great time, my adventurers experienced a diverse range of townsfolk, they got the clues they needed, and they spent an appropriate amount of time running in circles, confused, and lightly annoyed.
Best of luck, I really like that someone pointed out you are definitely on the right track just by identifying ways to improve. If your players are good players, they won't spend the whole night picking your tropes, cliches and otherwise apart. They'll be embracing the story. A big chunk of the suspension of disbelief rests on their shoulders, too. Keep tabs on players' faces, whether or not they appear restless or disinterested, etc. If you have them engaged and they're into it, don't stress so much if there is a cliche element. Change it up if you want and there's still a way to do so with that NPC/monster/event or just let it ride out like it is. I wouldn't overemphasize a need for each situation to be unpredictable. Too much unpredictability can seem chaotic, unstable and not very believable. There's few instances where a great wyrm innkeeper makes sense, for a ludicrous example. Another point: While there may be an occasional thin, well-kept and charming executioner among all the executioners employed by nobility in your campaign world, if you line them all up in a row most of them are going to have about the same demeanor and build. Sometimes cliches make sense. Half-ogre rogue: "Shhh! Be quiiiieeeet.. I'm trying to move silently.." THUDTHUDTHUD
Another important thing to think about here is delivery. Even the most worn-out cliches can feel impacting, meaningful, epic, and unique with a captivating delivery. Some of this might involve your own roleplaying abilities, some your confidence (though a decade of DM'ing is a good few belt buckles of experience as a trope itself), and some of it might involve engaging the player with why the cliche is relevant to the character. If there is a central dynamic to the plot going on that requires attention, focus and careful consideration, a cliche might help avoid distraction.
Also, I have found that many players begin to project assumptions and read more into what was originally irrelevant rapport and NPC depth when they are interested. In this way, they shape the plot themselves by giving me ideas over time and they end up feeling like they solved a puzzle by choosing the right NPC to focus on. Sometimes it is and I had something set up, but sometimes it is the players themselves deciding fate for their characters unbeknownst to the players.