Add more non-magical ways to get pets that are better than what your starting pets can level into. Such as pet stores with figurines, or being able to tame watchmen by paying them money, or by healing a monster at low HP.