I'd suggest a Githyanki melee Wizard. The character will start with a 20 STR and 18 INT.
Optimal would be to go Quarterstaff and Shield, with PAM as the 4th level feat. Take Booming Blade or Greenflame Blade, and Haste. Usual combat round (after Haste is up) will be to cast a leveled spell or BB/GFM as an Action, Attack Action with the Haste action, and then Bonus Action PAM attack. At 8th level take Warcaster, so that the character can use Booming Blade as a Reaction against anyone who approaches. Note that until the character gets Warcaster, keeping up Haste is going to be tricky.
Much less optimal (but still playable) would be the same spell loadout, but wield a greatsword and take GWM instead of PAM. Haste is even more critical with this approach, since GWM is dependent on number of attacks. Still take Warcaster at 8, but take Sentinel at 12 for more GWM attacks.
Finally, I know Paladin was excluded, but I'd like to point out that this character actually has the stats to pull off a Paladin/Wizard multiclass, which in some ways is even better than a Paladin/Sorcerer (other than needing so many good stats). Notable subclasses for this multiclass include Conquest (for Armor of Agathys), Abjuration (for Armor of Agathys shenanigans) and Bladesinger (for getting Extra Attack on the Wizard side and limiting Paladin to a dip, and Armor of Agathys shenanigans starting at Wizard 10.) Like a Paladin/Sorcerer the character gets Smite and tons of spell slots for combat, but unlike the Paladin/Sorcerer the character can take the Wizard's niche utility spells for out of combat, and benefit from the much-superior Wizard subclasses.