D&D 5E [5e] What to play in a 2-people group? Other character is a paladin.

[Zaruthustran]

I recommend a full caster.

Druid is a strong case, since Wildshape can address so many niches.
Wizard would be the classic combo. Might & Magic, and all that. Conjurer would be my choice.
Cleric is a natural fit if you both serve the same faith. That'd be fun RP. Light gives access to the big-damage Fire spells.
Bard and Sorcerer are harder to recommend, due to the limited spell selection.

 

[Herobizkit]

I always recommend Bard to anyone who says "I don't know what to play."

Thematically, a Paladin and a tough War/Storm/Life Cleric (the ones who can wear Heavy armor) would fit super-well together as a "buddy cop" duo. The two classes are sort of yin and yang; while the Paladin focuses more on fighting and the Cleric focuses more on casting, they both have access to the same armor and weapon proficiencies.

 

[RCanine]

Story-wise, the obvious answer is rogue. It's that trope of Noble Male, Roguish Male, but could also be Cop and Scientist or Big Guy, Little Guy or Guys Smash, Girls Shoot.

But I think ranger might be best: you're both tough, have healing spells and he covers str/cha/melee while you cover dex/wis/range. You will be able to cover each other's weaknesses pretty well, but you're not so different as to make balance impossible. Druid is a similar suggestion, but I think you want more skill monkey than caster: AOE situations in a two-person party should be rare, but you do want that person that can find and deal with traps and locked doors.

Race-wise anything that tends toward magic is probably good: high elf, forest gnome, tiefling

I'd probably do Tiefling for the contrast with Paladin with the following SCAG options:

• Feral (+2 Dex/+1 Int)
• Replace Hellish Rebuke with Burning Hands (AoE), or the Devil's Tongue (a few manipulation spells)

Or if you DM doesn't allow SCAG, High Elf (Booming Blade cantrip) for the spell and perception skill.

I'd go Ranger and be tempted by Beast Master despite it's mechanical problems because increasing your party size by 50% is no small thing.

 

[FrogReaver]

Sorceror. Twin spell in a two person party is too good to pass up. Invisibility on the whole party at level 3? Fly on the whole party at level 5? Polymorph the whole party at level 7.