Since the paladin gets the spells find steed and find greater steed, it only seemed natural to take this theme to its logical end: find greatest steed:

FIND GREATEST STEED
9th-level conjuration

Casting Time: 10 minutes
Range: 30 feet
Components: V, S
Duration: Instantaneous

You summon a spirit that assumes the form of the loyalest, majestic-est mount. Appearing in an unoccupied space within range, the spirit takes on a form you choose: a unicorn, a bulette, a felidar, or a nightmare. The creature has the statistics provided in the appropriate statblock for the chosen form, though it is a celestial, a fey, or a fiend (your choice) instead of its normal creature type. Additionally, if it has an Intelligence score of 7 or lower, its Intelligence becomes 8, and it gains the ability to understand one language of your choice that you speak.

You control the mount in combat. While the mount is within 1 mile of you, you can communicate with it telepathically. While mounted on it, you can make any spell you cast that targets only you also target the mount.

The mount disappears temporarily when it drops to 0 hit points or when you dismiss it as an action. Casting this spell again re-summons the bonded mount, with all its hit points restored and any conditions removed.

You can’t have more than one mount bonded by this spell, find steed, or find greater steed at the same time. As an action, you can release a mount from its bond, causing it to disappear permanently.

Whenever the mount disappears, it leaves behind any objects it was wearing or carrying.

A mount summoned with this spell cannot take legendary actions. If it normally would have legendary actions, on its turn, it can use its action to take one of its legendary actions.

A paladin can prepare this spell as they would normally prepare a 5th-level spell, but expends two 5th-level spell slots to cast it.

This spell would appear only on the Paladin spell list, and could be prepared and cast by a paladin once the paladin was 19th-level. Additionally, this spell would be available to an 18th level Bard via magical secrets. I think this spell only being available to 18th level and higher characters is going to be enough to balance it. Compared to true polymorph, the effects here actually seem pretty modest for a 9th level spell; and for the paladin, casting is always going to be limited to once per long rest, as it uses up all of their highest level spell slots.

The mounts I have chosen range from CR 3 to CR 5. The original 2nd-level spell find steed mounts range from CR 1/8 to CR 1/2, and the now penultimate 4th-level spell find greater steed provides mounts ranging from CR 1 to CR 2. These two spells are given a comparative analysis in this answer. This CR 3-5 range seems like an appropriate increase in power, but as with both its predecessors, some of these greatest steeds will be less greatest than others. I've carefully chosen four creatures for this spell, I feel that each brings something unique to the table, even though one of them seems to be a head above the rest. Speaking of which…

The Unicorn (CR 5)

If I'm being totally honest, this spell could have been called find unicorniest steed. The unicorn is easily the best mount on the list. It is not the best damage dealer, not even close, but the utility and support the unicorn provides is unparalleled by other creatures on this list. It can cast pass without trace at will, and its ability healing touch is equivalent to a 2nd-level cure wounds twice a day.

The unicorn is the only creature on the list with legendary actions. I felt that giving the unicorn unbridled access to its legendary actions was too much. Additionally, its just easier to keep track of things when I'm not keeping up with my own turn, my mount's turn, and legendary actions for my mount on other turns. Instead, the unicorn can opt to use one of its legendary actions on its turn. In particular the unicorn's shimmering shield ability is quite good, and allows the unicorn to excel in its support role.

The Bulette (CR 5)

This guy is the bruiser of the group. At +7 to hit for 4d12+4 damage, the bulette's bite attack hits like a truck, and AC 17 averaging 93 hp gives him respectable staying power. The bulette really gets interesting with his movement: burrow 40 ft. If you're nostalgic about catching your first diglet in a cave outside of Vermilion City, the bulette is for you.

The Felidar (CR 5)

The felidar packs a similar punch to the bulette with identical AC and hitpoints, but the felidar is for the more psychically minded adventurer. The felidar has the ability to form a special bond with another creature, granting these benefits:

• The felidar can sense the direction and distance to the bonded creature if they’re on the same plane of existence.

• As an action, the felidar or the bonded creature can sense what the other sees and hears, during which time it loses its own sight and hearing. This effect lasts until the start of its next turn.

Similar combat prowess as the bulette, but has some interesting abilities that make the felidar an excellent scout and great insurance policy if his owner gets kidnapped.

The Nightmare (CR 3)

This goth version of the pegasus features an ability that makes it better than his winged celestial brother, earning him a spot on this list. For the most part, the nightmare is identical to the pegasus, which makes him probably the weakest choice on this list. But the nightmare has one ability the earns him his place here:

Ethereal Stride. The nightmare and up to three willing creatures within 5 feet of it magically enter the Ethereal Plane from the Material Plane, or vice versa.

This guy can disappear to the ethereal plane at will. And he can bring his three closest friends. The utility of this ability is limited only by your imagination and how annoyed your DM is that your flaming horse can walk through walls.