I suppose you could have the pet have an xp meter, and each time it filled up (due to the player traveling normally with the pet) the pet would generate an encounter where the player could interact with the pet, and have a chance of leveling up the pet or player in some way?
the game tracks relations between band members and NPCs in a manner similar to The SIMs. i was thinking of making it do the same for pets.
in the way of spontaneous NPC triggered interactions for pets, about the only one i was considering was a "pet me!" action when the player was idle. or maybe coming up to you with their ball or a stick in their mouth - an obvious request for you to play with them. or maybe begging for food when you're cooking or eating.