On the small but vicious dog it says:

Dog recovers obedience in the same way characters recover fatigue and stress, using te owner's Animal Handling instead of Discipline or Resilience.

But you recover stress and fatigue based on toughness and willpower.

Or am I missing something?

You can recover Stress and Fatigue using Discipline and Resilience during a Rally step by making Easy (1d) checks.

Maybe after an encounter (or a night of rest) your companion/pet recovers Obedience equal to the owner's Fellowship.

That would make it the same as Stress and Fatigue across the board.