The average commoner is not likely to "own" their own horse (maybe a dog).
Another thought, is to maybe have horses and dogs available for "renting" in certain types of regions.
Maybe a fast horse (1.25->2.5 travel speed?) can be found in cities and towns and a good hunting dog (plus 10? to hunting/combat skill) in certain rurals. (a pigeon to maybe help locate and corner sages and wizards?[a more accurate report of sages/wizards within 2-3 regions of the advy]might be tougher to code?)
Could be daily or weekly rentals.
Some advies have the gold to spare and some do not.
Maybe advy's get a donkey. Then they can become Sancho Panza.