What you are concerned about is the normal damage curve of the game. It's ok for a player to nova occasionally. from the example you gave, the Paladin used a first and third level slot while maintaining an AC of 18 tops without magic. Compare that with a wizard casting a fireball for an average of 28 damage per target. If there are 2 targets, and why would you fireball if there is only one, the wizard just did 56 damage with a 3rd level spell. Now lets say the wizard has no armor or armor spell and is attacked with a base 16 dex. She can cast shield for an Ac of 18 and has now used the same number of resources while over a hundred feet from the battlefield. Both characters are effective offensively and defensively. The situation will determine which proves more effective at any given time.
Extend this to a fighter of the same level, using dual weild just to keep it simple and only one feat for dual weilding equivalent weapons. 5 attacks with action surge used and lets say 2 battle dice used, one for precise strike to turn a miss into a hit and the other for damage. for a total of 5d8+1d10+25 for roughly 54 damage using similar amounts of resources. this seems pretty close to balance and once again will depend on the situation.
If you are worried about balance the main source of imbalance is the Great Weapon Master and Sharpshooter feats. Vs. low armor opponents they can sway the damage way off the curve, but are not inherently imbalanced.
As many have said, the way to handle massive nova potential is to mix it up between a few powerful foes one encounter and then many weaker ones in another fight. Keep the style of the fights dynamic so different characters get to shine at different times.