@Jeff's answer is solid, just adding some perspective from my experience.
In my campaigns, I've never had a player complain because I added a bit of storytelling to how they acquired their animal companion. That being said, your campaign and play-style affects this more than anything. To give an example from an intensely story-driven campaign:
It took 2 or 3 sessions for our Paladin to gain his mount at 5th level, but it was worked into the encounters we were playing at the time, so the other players didn't feel left out.
The player of our Paladin expressed an interest early on about having a giant wolf to ride instead of a horse. I mentioned it in this answer, it has a bit more background on why.
The players were tracking a band of orcs through a dense forest in the
foothills of the Misty Mountains (LoTR campaign). They eventually
realized that the orcs in question were meeting up with a band of
warg-riders for reinforcements. The giant wolves in the area had been
hunted (so they could be turned into wargs by the orcs) and were not
very happy about it.
So when the warg attack was imminent, the Ranger convinced the wolves
in the area to aid the party. The alpha wolf's attack on the
warg-riders was a thunderclap, and he killed many of them, but was
surrounded. The Paladin (with no nudging from me) saw this, and
stormed to his rescue (forgive the unsubtle metaphor), but was too
late. The Paladin was in trouble then, being wounded and cut off from
the rest of the party, but the alpha's mate burst from the shadows,
stuck the wargs from behind, and bore the Paladin away from danger.
The party eventually defeated the warg-riders, but the beta wolf took
over the pack. The alpha's mate howled in mourning over the alpha,
and the party left. A few days later, the Paladin discovered that the
she-wolf was following him, when she came out of the shadows and laid
down next to him.
It wasn't a hard story to work into the adventure I already had planned, and all the other players really wanted to find their own special mount after that too. They began discussing how they would do it (in story terms) during each session.
It made the story rich, and I loved running it, but everyone has their own tastes: use your own judgement.
I guess I should mention, the "poof! you have a horse" thing was way out of character for this campaign, we were playing with a very subtle-magic style. Spells rarely had flashy visuals, magic potions tended to taste like mud. A horse (or wolf) just appearing out of thin air didn't fit.