What if instead of having a bicycle, there was an HM move that allowed you to ride a pokemon?

Which pokemon would you teach Ride to?

Rhydon seems like it'd be a pretty reliable steed. You could ride on rhydon.