Blindsight can "see" through the fog
Blindsight allows a creature to "see" through senses other than normal vision. The description reads (PHB 183):
A monster with blindsight can perceive its surroundings without relying on sight, within a specific radius.
Blindsight most likely counts as seeing for the purposes of a spell that requires sight. There are a couple of ways you can get access to blindsight:
Magic Items
The Dagger of Blindsight is a rare magic item from Waterdeep: Dungeon of the Mad Mage with the following ability (WDMM 86):
A creature attuned to it gains blindsight out to a range of 30 feet.
If magic items are available to you, you might ask your DM about obtaining this item. This isThere are also legendary items from the only official magic itemRise of Tiamat campaign which can provide limited blindsight (thanks Kirt for pointing these out), and there may be others I am awareunaware of that provides this sense, but I do not know what may be available in your specific game. You are already outside the realm of official books with the Oath of the Open Sea subclass, so there may be other unofficial options available to you.
Spellcasting
Draconic transformation is a 7th-level spell from Fizban's Treasury of Dragons available to druids, sorcerers, or wizards that provides the following benefits (FTD 19):
With a roar, you draw on the magic of dragons to transform yourself, taking on draconic features. You gain the following benefits until the spell ends:
Blindsight. You have blindsight with a range of 30 feet. Within that range, you can effectively see anything that isn't behind total cover, even if you're blinded or in darkness. Moreover, you can see an invisible creature, unless the creature successfully hides from you.
Breath Weapon. When you cast this spell, and as a bonus action on subsequent turns for the duration, you can exhale shimmering energy in a 60-foot cone. Each creature in that area must make a Dexterity saving throw, taking 6d8 force damage on a failed save, or half as much damage on a successful one.
Wings. Incorporeal wings sprout from your back, giving you a flying speed of 60 feet.
A downside of this method is that it uses concentration, so you would be limited to non-concentration spells if you want to keep the blindsight.
Wait it out
Another option is just to wait out the effect of the fog.
You state the fog "lasts way longer than any fight", but it doesn't have to. You can use rope trick to hang out in an extradimensional space for the 10 minutes, etherealness to pop into the ethereal plane for the duration, or use forcecage to trap the paladin until the fog effect expires (although with forcecage you have to wait the full hour duration as well, you cannot choose to end it like you can with the other two mentioned spells). You are essentially putting the combat "on hold" until you can fight on your own terms.