Befriend a druid/wizard/mystic theurge
The 5th-level Drd spell awaken [trans] (Player's Handbook 202) can be cast on an animal like a fox. The 5th-level Sor/Wiz spell Rary's telepathic bond [div] (PH 268–9) when followed by the 5th-level Sor/Wiz spell permanency [univ] (PH 259–60) can make the bond spell permanent (although subject to effects that dispel magic) between two creatures like a fox and a rogue. In combination, any animal can gain a reasonable Intelligence score and have a human with whom it shares a mental link.
Normally such a combination of spells is typically expensive and, in fact, impossible without DM intervention: an awaken spell has a price of at least 1,700 gp if cast by a level 9 druid, a bond spell 450 gp if cast by a level 9 wizard, and a permanency spell on that bond spell 12,950 gp if cast by a level 13 wizard. This last spell is beyond the 3,000-gp limit placed on spellcasting by the Player's Handbook on Table 7–8: Goods and Services (under subhead Spellcasting and Services on page 129), so only the DM can make that spellcasting available. The total price for all this done this way is 15,100 gp.
(While it's possible to tote around a little buddy from one caster to another to get these spells cast, a lone caster would cast all of them. A no-shenanigans druid 3/wizard 3/mystic theurge 10 could cast all three spells, but the total price rockets to 23,500 gp.)
While this is a substantial sum at low levels, the outcome is largely unspectacular. Adding the awaken and permanent bond effects to a cat (Monster Manual 270) or fox (Dragon #323 98 has the fox using cat statistics) technically gives the creature an LA of at least +2 (normally a cat's LA is +0 as per Dragon #293 54), but I don't think anyone but a low-level commoner would argue that such creature was the equal of even, for example, a level 2 fighter. This DM suspects that by the time the PCs hit level 3, such a creature really won't be a combatant anymore but just a fairly smart, tougher-than-it-looks-but-it-doesn't-look-that-tough, semi-telepathic magical beast, suitable for light scouting and not-particularly-dangerous guard duties.
Survey some constructs
Similarly but slightly sideways, this DM assumes most creatures created by the feat Craft Construct (MM 303) can be given the command by their creator Obey the commands of this creature. (Transferring control of a creation should be possible even if the game doesn't mention explicitly how; that is, many creations have prices in case some dude wants to just straight-up buy one.) While this typically won't establish an empathic or telepathic link (unless it's Golden the clockwork cat!), Pathfinder—D&D 3.5e's respectful cousin—includes this nifty additional rule in its homunculus entry:
The person whose blood is used to form a homunculus’s body becomes its master; it is possible for one person to give blood for the creation, another to sculpt the base material, and another to magically animate it as a minion for the one who provided the blood.
While this rule is absent from the 3.5e homunculus entry (Monster Manual 154), it is an easy, interesting, and not unbalanced house rule… and it's precisely the kind of secret knowledge a grateful high-level patron could reasonably possess.
(By the way, to be clear, this DM doesn't mandate that a traditional homunculus be a misshapen horror: This DM takes the idea that a "homunculus’s creator determines its precise features" further than most likely do, letting it mean that the creature must be about 18 in. tall, have a 2-ft. wingspan, and possess a mouth full of needle-sharp teeth but putting pretty much everything else under the creator's control. Wizards have a hard enough time socially from constantly carrying a satchel filled with bat poop and spiders; no need to have wizards further ostracized for surrounding themselves with little hideous winged frog monsters!)
Use an original magic item that follows published guidelines
An original magic item that grants the feat Obtain Familiar (Complete Arcane 81) has a price between 20,000 gp and 30,000 gp according to the Arms and Equipment Guide on Magic Items that Grant Feats (128). Strictly speaking, this DM would usually use the higher price if the magic item's possessor need not still meet the prerequisites of the feat granted by the magic item, but this DM would adjust the price for the campaign, making the price lower if every PC has a pet, for example, and, perhaps, making the price higher if some typical drawbacks of the granted feat didn't apply. (For example, while magic is weird sometimes, it seems particularly odd to this DM were a creature to employ, like, a headband of familiar summoning to obtain a familiar and the familiar dies that the creature that used the headband is forced to wait a year and a day to summon another familiar… but another DM's opinion may be entirely different.)
This solution still requires some homebrewing, but even though the nuts and bolts of such an item will be up to each DM, at least pricing guidelines—however subjective—are out there.
Discover a companion during an adventure
More than a few creatures possess telepathy and are willing to throw in their lots with adventurers of the same stripe. A pseudodragon (Monster Manual 210–11) is a perennial favorite, for instance, joining good-aligned adventuring parties since at least 1978.
Further, any living creature that possesses at least 6 Hit Dice and a Constitution score of at least 13 can have two feats—Shape Soulmeld (shedu crown (Magic of Incarnum 85–6)) (MoI 40) and Open Least Chakra (crown) (MoI 39–40)—that, combined, allow the creature to communicate telepathically with any creature possessing a language. An generous DM can make such a creature available to the PC—maybe such creatures are bred by a soulcaster (MoI 142–7) or occur naturally in areas steeped in incarnum?
A discovered creature may just be a temporary adventuring companion but could, over time, develop into a more permanent cohort. (A cohort needn't only be a product of feat Leadership (PH 97)—the feat is just usually the easiest way to get one; for details see this question.)