I'm just copying-and-pasting a bit from the homebrew stuff I'm working on that I think has relevance to this (obviously not 5E specific).
An example of a bad challenge might be one where the objective is to “convince the king to give us his sword”, and the characters are expected to continually make diplomacy checks until they have successfully convinced him. This sort of challenge is both narrow (it only allows for a very limited set of skills to be put to use) and shallow (convincing someone to do something is fundamentally a “yes or no” type situation - it should be modelled by a single check, not a dozen of them). It will result in only a small subset of the party (the social characters) being able to contribute, and even for them, it will be repetitive and dull.
It’s boring because it is intensely focused on a simple objective, that cannot really be broken down into steps. What we need to do is expand the challenge by broadening its scope beyond a single discussion. The party still needs the king’s sword, but the king has a counsellor who has his own eyes on the sword, and the party needs to overcome his various machinations - blackmail, threats, poison, sorcery - and expose his corruption before the king will consider their request.
Our skill challenge now has width. Instead of just being about diplomacy, it can incorporate skills around deflecting blackmail, resisting threats, detecting and treating poison, unravelling spells, reading people, investigation, stealth and diplomacy. At the same time, it has become deep - the situation provides enough obstacles that each success progresses the party past one, and into another. The GM can reply with something like “after successfully foiling his attempted blackmail, it appears the counsellor has turned to other means to counter your influence with the king - roll a perception check to see if you notice the poison in your breakfast.” instead of “the king looks one-sixth more convinced”.
I'm not really familiar with the Redbrand encounter, but reading between the lines, it seems like it's the sort of thing (winning over an entire mercenary band as allies) that is unlikely to be the result of a single Persuade roll. If the party (the whole party, not just the social character) agrees to pursue the social solution to the situation, it should result in a significant challenge for the whole party, not just a skill check for the Persuade monkey.
Divide the Redbrands into factions - one pro-party and one anti-party. Invent named NPCs to represent both factions. The party needs to woo one, and thwart the other. Think of curve-balls that the anti guy will throw in to the situation, and get the party to improvise solutions to them. This can be hard to throw together on the fly, but if you have some time, it can make a challenge like this much more believable, and enjoyable for everyone (instead of just the one person).
If the whole party doesn't agree with the social solution, well, it's hard to persuade people to be your friends while your other friends are trying to impale them on various pointy things.
