NPCs is good. At one point, I had two players (A cleric of Luck and an Illusionist). So, I squirted an NPC Fighter/ranger, who's still with the party, to help them out. Every other NPC in the party was per adventure (They need to hire a trapmaster to get them through, Paladin leading them into caves under the city, etc).
If you want to still go solo, then I agree with what's above. But class depends. A Bard may have an easier time in a lot of situations (Depending on how the bard is geared), Especially roleplaying. Putting a lot of RP in there will really help out.
Also, if there's a task that they need something their class cannot, an ability (And consequence) could be offered for them to get out. For example, they're playing a bard, Wiz/Sor, etc, and they're challanged to a fight, allow them to back down. However, it'll likely have reputational backlashes, they could be hastled where they live, etc.
If it's a 10th level paladin, he should be able to handle himself. Also, getting a squire or cohort (paladin in training, etc) would bre reasonable.