As other answers pointed out, the rules for mounts (in the Basic Rules, under Mounted Combat):
A willing creature that is at least one size larger than you and that has an appropriate anatomy can serve as a mount, using the following rules.
conflict with medium-sized characters using the the pony or a mastiff, from find steed spell:
the steed takes on a form that you choose: a warhorse, a pony, a camel, an elk, or a mastiff
and also the peryton, from the find greater steed* spell:
the spirit takes on a form you choose: a griffon, a pegasus, a peryton, a dire wolf, a rhinoceros, or a saber-toothed tiger
I think you can argue in either direction, that the spell definitions take precedence, or that the rules for mounts take precedence.
It Happened to Me
I actually had almost the exact same situation.
The solution I chose was for the paladin's mount to conform to the stats of a warhorse, but appear to be a large-sized mastiff.
One of the characters in my campaign is was a foundling protector aasimar taken in by a halfling priest of Pelor and raised in a halfling community. As he grew up, he felt the call to be a paladin. Realizing that his mere presence was putting his adopted village in danger, he packed up a cart and was preparing to haul it off. His mount showed up. Yes, I know 1st level paladins can't cast find steed, but it was such a great narrative moment, and so the steed answered the call that he hadn't even made yet.
Me: Your steed shows up. You know intuitively that if it goes away it
won't come back until you can cast the spell.
Player: What does it look like?
Me: Well, I assume, a warhorse, but you can have it appear any way the
spell says. In fact, the spirit communicates to you that it wants to
manifest as a warhorse but it will choose to appear as an old broken
down carthorse, so as you not embarrass itself, pulling a cart and
all, and to keep a low profile.
Player: I want a mastiff.
Me: But you can't ride a mastiff. You're too big.
Player: I was raised a halfling. I want a mastiff. A warhorse will
scare the village.
Me: But . . . you're too big. You can't ride a mastiff.
Player: I think of myself as halfling-sized.
Me: But . . . you're not. You're medium. You can't ride a mastiff.
Player: How about a large-sized mastiff?
I almost gave in on this one. I'm still not sure it wasn't the way to
go. I was concerned about the effects of scaling a mastiff up.
Me: Well, tell you what. It's actually a warhorse, but it looks
like a large-sized mastiff. In every way it is a warhorse, except it
looks like a mastiff.
Player: Okay! Hooch, fetch the cart! Let's go!
So, the solution I chose, was to allow the large-sized mount to appear as a large-sized version of a medium-sized mount, while conforming to the stats of the large-sized mount.
Of course, you could just let the medium character ride the medium mount, and ignore the mount size rule. Narratively it might look a little silly.
Or, size up the pony, mastiff, or peryton to large, either with or without scaling stats. In effect, the pony/mastiff/peryton would actually just be size large, and thus suitable for a medium creature to ride.