My Breton Rogue's traveling companion is Jenassa. Someone's gotta save his a** when he goes Giant's Toe collecting the wrong way.
My Breton Battlemage usually travels with her housecarl/BFF Jordis, but lately it's just been Trigger, her horse from Lakeview Manor. Early on her game, she traveled with Marcurio. After she became Arch-Mage she took each of the students under her wing and traveled with them for bit. Onmund's still walking around the college naked because she paralyzed him and them spam-pickpocketed his robes and hood so he'd wear a circlet and robes she gave him instead, and she keeps forgetting to give him his robes and hood back (they're in the Arch-Mage's Quarters).
My Dunmer swordswoman likes traveling with Marcurio or Kharjo. She's a professional and didn't have much patience for anyone else. She likes Jenassa but she got sick of everyone asking if they were sisters. She recently bought a horse at Whiterun, and named him Serjo.
My Redguard spellsword was strictly a Marcurio girl. Marcurio's always up for a pint of mead at the nearest tavern and a bit of drunken mischief--and he always waited patiently outside the jail for her to be released--so they made a good match.
My Bosmer ranger first traveled exclusively with Faendal, then Marcurio, who he ended up marrying. For a while he traveled with Mr Whiskers, a stray dog, but then the Thalmor killed Mr. Whiskers and my Bosmer grew to be a very bitter elf afterwards. Later he joined the TG and pretty much only traveled with Gypsy the Grey, his horse from Windstad Manor, who he neurotically protected from any heartless, innocent beast-killing Thalmor.