Corrupt souls stained black
Blood gifted in sacrifice
Warlock ascended!
Note: While this discussion is focused on the 5e Warlock class, it is also relevant to a number of its OSR siblings, namely the Accursed from Worlds Without Number, though I've seen a few other homebrew classes floating around with basically the same problem.
Aesthetically, most Warlock classes are built around pact magic, the classic Faustian bargain made with a demon, fey, or outer god. The fantasy of the class is that a PC is operating within the pact. Warlocks must Tiptoe around a patrons poorly worded orders in order to both keep a hold of their morals and their power, if only barely. It's compelling! Dramatic! Intriguing! It is also horribly implemented.
In my first time playing 5e, I played a Warlock with the Pact of the Great Old One. The idea of playing a character in contact with dark powers fascinated me, and my DM liked the idea as well. The fantasy was wonderful. The reality was most assuredly not. The problem was the Great Old One (GOO) my character pacted with, was not some distant Elder Thing with no real interest in what it’s Warlock was doing. It understood, at least in broad strokes, when I wasn't doing what it wanted, and would take away my power if I went against it. This had the effect of hobbling my character. Carrion was constantly dealing with his patron’s attempts to seize control and wreak havoc on the world around him. He suffered random hit point loss and siezures, and at several points he lost his powers for the majority of a session. This was not the awesome character I'd envisioned. Carrion was a crippled wreck, who struggled to accomplish even the smallest task. It was great storytelling, but terrible gameplay.
Now, unbeknownst to both myself and my DM, this was not how the Warlock was meant to be played. Errata published later mentioned that Warlocks aren't at the mercy of their patron mechanically. A Patron can't rescind their pact at a whim, taking all their knowledge and power back with them. This though, introduces a different problem. By removing a patron's ability to control their warlock, you remove their majesty, their teeth. It puts all the power in the hands of the PC and raises a whole host of new questions.
Questions like, "So, I can just tell the Lord of Hell to piss off, and he still has to give me power next time I level up right?" and "So, the Lich I just dealt with, he realizes I'm a jumped up peasant with nothing to offer, right? Why would he just agree to teach me magic?" "So, I know I just pinky swore to the Angel that I'm not going to hurt people with my shiny new cantrip, but this kid just kicked me in the shin, so I'm going to kill him." These are the sorts of issues and questions that Warlock design in its current form has to deal with.
If the patron can't rescind the pact, it really does become like the Chuck Norris joke. "Chuck Norris sold his soul to the devil for his rugged good looks and unparalleled martial arts ability. Shortly after the transaction was finalized, Chuck roundhouse kicked the devil in the face and took his soul back. The devil, who appreciates irony, couldn't stay mad and admitted he should have seen it coming. They now play poker every second Wednesday of the month."
This is proved out in my current 5e game, where I am once again a GOO Warlock. There my patron is little more than a reason for my character to be participating the current adventure. He's a side note, a flash of color. Aesthetic. He has no method with which to hurt me, and if I did disobey him, the best he could do was send someone after me. He can't keep me from the secrets of the universe. He already gave them to me.
This is, I suspect, how the Warlock is actually meant to be played. Mechanically, it is worlds better, but in terms of storytelling and narrative beats, it's a massive downgrade. Carrion was a much more interesting character because of the horrible things he was going through. When he decided to do the right thing, it mattered, because it cost him. Challenging his patron was a big deal. In the current campaign though, my Warlock’s Patron is functionally irrelevant to me. My character may be concerned, but there's no mechanical teeth to pissing him off. He's a non-factor. I've lived both fantasies, and largely, neither have proven to be fantastic. This isn't an issue of poor DMing, this is instead an issue of poor game design.
To summarize, the way 5e and WWN turn the Warlock fantasy into a class forces one of two possibilities: either you can prioritize the Warlock narrative at the expense of a Warlock’s power, or you can prioritize the Warlock’s power at the expense of the narrative. This is not going to be an issue in every game. Or even most games. Some groups don't need a patron to be much more than a quest generator. Other groups just want to have a good time with friends and like the aesthetic. However, if players want more, they will struggle to get it. In that way, picking a warlock class is kind of its own Faustian bargain.
So how do we as GM's fix this? It's simple: Identify major players within your world who could reasonably be a Warlock’s patron, then when PC's perform a service for the patron, allow them to pick up a feat or foci as a reward.
So, let's break this down. Step 1. Let’s determine who qualifies as a patron. Ideally, a patron should be both exotic and powerful in relation to the PC's. In most campaigns, things like Dragons, Liches, Fey, Angels, Demons, Aboleths, etc. all work. In other campaigns such as one taking place in Kevin Crawfords' Latter Earth setting, a patron might be an ancient AI or a powerful outsider. In Dolmenwood, it might be one of the Wood Gods or the Hag. Even the Nag-Lord or the Cold Prince could work if the party approached the situation correctly.
Once you've identified who likely patrons are, you can move on to Step 2: determining what the patron wants. Depending on how thorough the setting you are using is, this can be more or less difficult. Dolmenwood for instance makes this easy. Everybody in the setting has a desire listed, just turn that desire into a quest or series of quests, and the work is done. However, if you are running a homebrew setting, or your intended campaign doesn't list what the major NPC's want, you'll have to do all that work yourself.
With desires determined and patrons identified we are ready to move on to Step 3: The Reward. For games like 5e, or WWN I recommend using a feat/foci and re-flavoring it to make it unique to the patron. Whether this is a specific foci that all party members get or something specifically tailored to each party member I'll leave up to you, though I recommend tailoring each gift if possible. You want this to be something the party member in question doesn't want to give up, but could if they cross their patron in the future. This is why we are going for feats rather than something more powerful. Feats rarely make or break a build, at least not on their own. Losing one is painful, but not usually critical, especially not if it was a bonus to the usual progression.
Note: It is extremely important that you telegraph to players that any power earned in a pact is something that could be taken away or used against them if they don't wield it wisely. Acting against the patron has consequences. That's the whole point of this exercise. This is the Patron's power being borrowed by the PC's. It is not the PC's power.
Finally we have Step 4: The Balancing Act. Assuming the PC's took the power offered to them, there should be consequences for that. If they took the power from an Angel for instance, they might have to operate as the Angel would if they want to keep that power. On the other hand, taking power from a demon might see the church turn against them. The gift of one Fey lord might cause another Fey lord to take offense, and so on. Rare is the gift that doesn't have consequences, and parties that take such gifts may in fact find them to be curses instead.
Let's end this post with an example: The adventuring party known as the Sanguine Sanctum is off on a quest to destroy the crystal heart at the center of the lost dwarven city of Kable Krutz-Mgar. Everyone is level 5, and that seems like enough for this not-so-simple quest. Deep within the bowels of the city they run into the demon Belshazzaroth. A powerful force in his own right he could easily take on a 12th level party. He's 9 ft. tall, His muscles could make The Rock hide in shame, Belshazzaroth's horns would look as though they should be lovingly fondled by members of a harem, or as though they are meant to gore legions of innocent victims. His body is painted a very aesthetic light red, and he is dressed in nothing but chains.
To the party's surprise, Belshazzaroth isn't interested in fighting them. Though sinister and undoubtedly evil, he is a connoisseur of ruins such as this, a demonic Indiana Jones, if you will. He is looking for a plain silver circlet that was lost in the cisterns. If the party would go and get it for him, he would reward them handsomely.
The Sanctum, never ones to pass on a job no matter how morally dubious, feel their ears prick up. "What kind of reward?" they ask.
"What kind would you wish for?" Belshazzarath smiles, his pointed teeth gleaming in the dim light. "I have many powers I could grant you. Gold is so... pedestrian, don't you think?"
The GM informs them that if they help Belshazzarath he will let them each pick one foci from the rulebook, and add it to their character sheets as a bonus.
The Sanctum goes back and forth, but eventually agrees to the Demon's request so long as they are allowed to keep any treasure they recover that isn't the circlet. The demon gives wide grin and agrees. A few days later, they return, waterlogged and frustrated but with the circlet in their possession. Belshazzarath is pleased, and grants them each a foci of their choosing before leaving with a smile and a warning: If they tell anyone what the demon was up to, he'll know, and there will be... consequences.