An idea for managing the amount of time spent on interacting: there could be smaller voting blocs among the NPCs who share a particular interest. Like maybe there's a group of 3 undecided who need assurances of protection against giants, a group of 4 who are only siding with claimant A because he's bribing them and only need a bigger bribe to switch allegiance, etc. It then becomes a matter of speaking to their representative rather than each member.
You should probably still take into account the likelihood of success for any given interaction when determining specific numbers of determined and undetermined voters, and that's what really complicates the matter when trying to arrive at a 'balanced' social challenge. If we assume a 65% success rate (the baseline "average difficulty" success rate baked into 5e maths), the PCs win 99% of the time. Basically, treating the undecided voters as easy to persuade will trivialize the encounter. This is assuming the PCs don't make a claim themselves, by the way.
The thing I sense most people are missing in this equation is that the PCs don't really need to persuade any undecided voters who are already on their side. There are confounding elements in play, such as the NPC claimants getting to convert them as well, but to provide the most simplistic view of the problem I see, I'm ignoring that for now. The only actors who matter are the undecided voters who disagree with the PCs' choice. Using the figure of 12 undecided voters who are evenly split, the PCs have already won 11:6, and that's before any attempt to persuade them has occurred. Using 65% success rate, it becomes 16:2.
In my estimation, the numbers need to start out stacked against the PCs' candidate. I don't see any other way around it. I would have all (or most) of those undecideds default to voting for a single claimant - the one the PCs haven't chosen. Perhaps he has the strongest claim, even if it's not signficantly stronger than the other claimant's. Unfortunately, I don't have any good ideas for ensuring the PCs wouldn't just switch sides once the stronger claim is made known.
Moreover, the target success rate for converting undecided voters to the PCs' preference needs to be below 50% or the overall odds of success are far too high.
Soooooo, something like this:
5 PC votes for claimant A.
4 NPC votes for claimant A.
4 NPC votes for claimant B.
0 undecided NPC votes defaulting to A.
12 undecided NPC votes defaulting to B.
<10% chance to convert claimant B's hardcore supporters.
30% chance to convert the undecided supporters for claimant B.
This will give the PCs 0-1 hardcore conversions, and 3-4 undecided conversions, for a total of 12-14 votes (5 PCs, 4 determined, 3-5 converted). They require 13 to win. Clever ideas and strong role play can be rewarded with advantage or other bonuses, increasing the likelihood of conversions. Laid out like this, hopefully you can determine for yourself what's the best number of voters. You can easily decrease the NPC votes defaulting to B for that purpose, or increase those defaulting to A if you don't mind extra NPCs in play.
Again, this is all assuming the PCs don't make a claim themselves.
(if my math or assumptions appear wrong to anyone, please point it out. A lot of this is coming off the top of my head)
(edit: went back to recheck and made some adjustments to illustrate my point)
Interesting stuff, thanks for taking the time to post it! My skills are lacking in this department so I like reading about the maths under the hood as it were. I have something of an intuitive sense of things when it comes to difficulty and challenges, but it's neat to see the maths spelled out.
In general, I don't specify a DC in my preparations because I think that puts the cart before the horse - after all, I can't decide on a DC until a player states a goal and approach with an uncertain outcome. That said, if I do call for a check, it's going to be DC 10, 15, or 20 usually. That'll be a straight roll for swaying an undecided voter unless one of the claimants is trying to thwart the PCs' efforts in which case it will be an opposed check. Both claimants have a +6 to their respective ability checks in this regard. So call that a DC 16 or 17 depending on however you want to round. They will tend to oppose the most charismatic PC during the challenge, but can't be everywhere all the time, leaving open the possibility that other PCs can go off on their own to sway voters and perhaps have an easier time of it. I think this works well because it encourages more than just the "face" to interact and creates a more dynamic scene.
A successful result in swaying a voter (check or not) means that the voter is now "decided" for whomever the PCs are advocating - let's call that a "partisan" for ease of reference. A failure means that the voter is now a partisan for whomever the PCs are opposing. Attempting to sway a partisan is always at disadvantage if there's a check and there are no retries after a failure to sway a partisan - they are locked into their position. So everything is based on the PCs' results - the claimants won't be engaged in the same way as the PCs which should take less time to resolve. Every failure the PCs make is a success for a claimant.
Here's a further complication: A claimant opposed to the PCs (which could be one or both claimants) becomes an Antagonist. In my games, an Antagonist has personality traits, ideals, bonds, and flaws just like the PCs do. Players in my game can "claim Inspiration" whenever they play to their personal characteristics, limit one per category per session. Antagonists can effectively do the same - I portray a personality trait, ideal, bond, or flaw and "claim Villainy," again, up to 4 times. While the players can spend their Inspiration to give their character advantage, the DM can spend Villainy to impart disadvantage on the character's d20 rolls. So, in addition to opposing the most charismatic character, there is also the option to impart disadvantage on a roll by spending Villainy up to 4 times. Or up to 8 times if the PCs are opposing both claimants by making a claim for one of their own.
That said, the players have an option to prevent the Antagonist from earning Villainy. If they are able to figure out an Antagonist's personal characteristics before they are put on display, perhaps by observing mannerisms and body language and making a successful Wisdom (Insight) check, it stops them from gaining Villainy by playing to a particular characteristic. So, for example, if the insightful fighter PC hangs back during the talking and observes the Antagonist, he or she might be able to figure out the NPC's bond. Now the DM can't play to that bond to earn Villainy. This encourages the non-charismatic players to engage in the interaction and help out and, in general, sets up an incentive to figure out the NPC's hidden motivations and traits.
How does that look in terms of difficulty to you now?