To have people 'looking forward to' ride a chocobo, i think level 20 is reasonnable. Too early would remove any 'urge' to be bale to ride one when seeing the others and level 30 maybe a bit too late because of the time it takes to get there (for the most impatient ones).