You get your next Talent at level 3 I believe it was and then it's every 3rd/4th level after that, something like that.

In short, you can get Pet Pal easily just doing some exploration of the first town.