So far the suggestions seem to be covering what you don't have and making the paladin better. I offer a counter suggestion; Do similar things to the paladin but differently. For this I would suggest a str based melee ranger.
Ranger gives you exceptional aoe and defensive abilites so you can stand side-by-side with your pally buddy and not worry about him having to "protect" you. His buffs make you hit super hard, and using a shield+Javelin(dueling does work with thrown weapons RAW/I) you can still cover range fairly effectively. Basically you guys should focus on being hard to kill melee powerhouses in my opinion, if there's a ranged problem, chuck a Javelin and ensnaring strike at it then walk over and smash them. Paladin buffs like crusader's mantle mean your whirlwind attack+horde breaker hit like a truck, plus you can use ensnaring strike to give him advantage/restrain an enemy for a while.
Your friend going vengeance and using a polearm he probably isn't going to be super defensive, I would expect a high str, then maybe con/cha, great weapon fighting fs and mostly feats to hit harder(that's my experience with polarm users and veng pally's in general). So you can't count on him to be very defensive. Honestly you may need to drag his butt out of the fire from time to time.
If you need more defense go level1 fighter for defensive and heavy armor, maybe even a 2 level dip for action surge once you have Whirlwind attack(this would also mean you don't need a +2 in dex which is big). Add on top of that Multiattack defense, and evasion eventually and you two will be nearly unkillable. For stats I suggest Prioritizing Con->Wis->Str, wis mostly so your dc on ensnaring is high, it's a shame to waste that spell. Con is a big deal for a two-man party and I would even suggest he go Con-Str-Cha or cha over str. You two will be able to take on way more epic challenges and get through it if you have more health. Remember you can only do damage while you're alive!
Personally I would never play a low-hp ranged damage dealer/Mage in a two person group, your paladin friend will not be able to keep people off of you and you will end up in melee more often than not, in a larger group you can get away with it but with two they are coming for you too and you need to be ready.
P.s. being a two-man party most of the time you will be out-numbered, and in 5e that's bad. For your paladin friend I would strongly suggest Magic initiate into warlock for Thunderclap/Blade whirl and Eldritch blast/Frostbite, and whatever L1 spell he wants, Earth tremor is pretty good. This will give him a great aoe option when you guys get knee deep in baddies and give a solid ranged option. Also Heavy armor master really helps when outnumbered(if you go fighter you could get this too).