I have nothing against animal companions of the heroes- done properly. They tumble into clichés too easily.
1) Only pretty animals need apply. For most authors, that means horses, wolves, hawks and falcons, dragons, or cats. And not for practical reasons, either, such as the horse being able to carry the hero or the hawk being able to hunt food. They're cuuuute, so they get a free pass. When was the last time you saw a heroine with a swarm of cockroaches? Or, for that matter, a hero with a pig companion instead of a cat or a wolf? I've heard people say that would be ridiculous, but I don't see why a pig talking into your head is inherently sillier than a pretty white horse with blue eyes doing the same thing (*coughcough*Mercedes Lackey*cough*).
I've heard other people say these animals are the most intelligent ones. Bull. Pigs are smarter than horses, dogs, or cats, and if the heroes really were going to choose the cleverest animals to accompany them, then they'd be out with dolphins, gorillas, chimpanzees, or African gray parrots. Animals like horses are the animals that have been used, and they're acceptably cute. So other authors use them, and then the cliches overrun the fantasy.
Point being: Ask yourself if you really need a wolf to accompany your hero, or if you're doing it because ohmygod wolves are cool.
2) The animals are anthropomorphized out of existence as animals anyway. Most of the time, the author could replace the animal with a complacent human sidekick, and I wouldn't notice the difference. The animals have no unique qualities. They might gesture a few things, like a wolf baring his teeth, and have a few sounds like snarling, but that's it. They do things no animal can, such as smiling or crying, in a human's mind, and they are perfectly good and loyal and obedient to whatever ideals the human has (see point 3). No matter what animal the author chooses, that animal ends up acting like a perfectly trained dog who can also understand human language. What's the point?
If you want to write about a relationship between a human and an animal- more to the point, a relationship between a human and a telepathic, intelligent animal- think about the differences between them. Why would the human's ideals or goals be important to the animal? Why would a horse keep galloping instead of grazing to fill his empty belly? Why would a wolf abandon the hunt and come running to a human's whistle? Why would a hawk fly until he fell from the sky instead of pausing to rest his wings? If you do intend them to have personalities, then give them their own reasons for appreciating whatever their companion's trying to accomplish. Otherwise, they end up what they are in most fantasies, a passive mirror reflecting the hero's personality.
3) When they do have any personality, it's always the same. The telcoms are good, obedient, loyal, dependent on their humans, and clever only in the service of the hero or the quest. (They're also a handy out in circumstances where everyone else gets captured and the hero needs someone who can sneak in unnoticed). The heroine's falcon doesn't ever snap at her or anyone else, and he's never reluctant to give up his prey or return to her, even though those are traits of falcons trained to hand. As I said in the previous point, the telcoms give up all hint of animal personality when they become telcoms, and the personality they get in return is canned.
Just once, make the relationship more complicated. Perhaps the telcom snaps or snarks at the heroine as well as at her enemies, and doesn't constantly declare his faith in her when her spirits flag. Perhaps he doesn't especially want to help her, and wanders off at unpredictable intervals. Sharing minds is probably stressful some of the time, especially when one partner's in a bad mood, and not the perfect endless love a lot of fantasy authors portray it as. Let the telcom and the heroine argue. Make the grumbles more severe than the "Oh, I wanted to eat him!" that passes in a lot of telcom fantasy as "clever" banter. Most authors apparently want their telcoms to exist as true secondary characters, not shadows or extensions of the heroes. If you do that, then make them exist, and have lives and concerns of their own outside the hero.
One author who does the telcom relationship very well is Steven Brust. Vlad Taltos, the hero of one of his series, has a jhereg (flying poisonous lizard that feeds on carrion) named Loiosh, who is telepathic and his familiar since Vlad is a witch, but not Vlad's lovey-dovey companion. Loiosh snarks at everyone, including Vlad, and though he's very loyal, doesn't declare it all the time. He also gets upset about decisions that Vlad makes, and his mate, Rocza, has even less concern for human feelings. This makes Loiosh a true character in his own right, capable of acting independently from Vlad, and not just reflecting him emptily back.
4) Telcoms never suffer from natural danger. The cats don't get chased by dogs. The wolves don't get shot by hunters. The horses never founder or get sick. The bad guys might kill them and give the heroine a chance to cry fake tears before she marches to her equally fake victory, but everything else that could happen and usually lurks below the surface waiting to pounce is somehow sent far, far away.
This makes even less sense in most cases than it would if the heroine simply walked through a town with an openly telepathic wolf at her side, since some telcom fantasies are obsessed with secrecy. No one must find out that the heroine talks to a wolf, for whatever reason. So the hunters have no reason not to shoot a dangerous beast who shows little fear of humans and is lurking around the village. Yet they don't. And if they express fear of the animals, dragons included, after finding out about the telepathy, the heroine castigates them. How dare they be afraid of a growling dragon big enough to swallow them whole and capable of charbroiling them first? He's her fweind!
5) Telcoms disappear whenever the author needs them to. Whole chapters can pass without mention of the falcon that the heroine sent away to scout, or the magical horse the hero left on the boundaries of the town. Somehow the animals never resent the treatment the heroes give them, always perform their assigned functions, and find their human companions perfectly. Nor do they ever have trouble finding food, even in a heavily settled valley, or accommodations, though the horses seem to get left at the door of the inn more often than put into stables.
If you don't attend to any other level of reality, at least attend to this one. Animals need a lot of care, particularly if they're large animals like horses, wolves, or big cats, and letting them loose in the middle of a crowded city is not a particularly good idea. What happens if someone steals them? If someone recognizes the animal and concludes the hero must be in town? If the hawk can't find enough to eat and becomes sick from lack of food? None of these wind up happening, but only because telcoms seem invisible and insubstantial when the spotlight moves off them. This happens to human secondary characters, too, but at least the humans can walk into an inn and order a meal, even if it's not the one the hero is supping at. Telcoms can't take care of themselves that way.
6) Telcoms tend to function too often as talismans. This happens with both Mercedes Lackey and Anne McCaffrey. It's not really the bond with a Companion- pretty white horse with blue eyes previously mentioned- or a dragon that's important to the story. It's a gratuitous sign that the hero is Cool, instead, and grants him entrance to a "special" groups where people have amazing mental powers and privileged positions and freer sexuality than the rest of society. It's one more twist of the ultimate teenage wish fulfillment fantasy. The heroes and heroines are often abused, mistreated, or too good for their families, but everyone around them refuses to acknowledge their uniqueness. Riding off with a Companion or a dragon is a symbol of that uniqueness, and the family usually bows down and is appropriately humbled.
In time, if you have a group like this, the focus moves off the group's existence and to how Special the heroes are. The Heralds help keep the peace and solve crimes in Mercedes Lackey's universe, but most of the stories aren't about that. They're about the Heralds getting Appreciated and having sex instead. Similarly, McCaffrey's dragonriders spend some time fighting Thread, the menace the dragons were created to fight, but it declines as the books go on, and more pages are spent on who's sleeping with whom or who's having kids with whom than on the training or the fighting or the bonds with the dragons. In both cases, the telcoms become comforts to their owners, sounding boards, the perfect understanding friend. The telepathy is just one more amazing magical power, no different than any other.
Doesn't that rather cheapen the presence of the telepathic animals in the story?
I recently bought a book that looked interesting, and only after I bought it did I realize that the book talked about the heroine bonding with a special hawk who "needs" her. I'm now scared to start it.