Without digging into the rules on when your animal companion acts relative to your initiative, I'd say your Surprise Attack feature has no impact on whether the enemy is flat-footed to your minion.
What you probably can do though is have your animal companion roll stealth when initiative is rolled, under the assumption that if you are Avoiding Notice your pet probably is too. If the pet minion's stealth check beats the perception DC of your enemy, I'd say they begin combat unobserved or unnoticed.
Now, even if this happens, they likely won't be able to take much advantage of it without an ability like a cat's Pounce, because you become observed if you end an action outside of cover or concealment. So it moves out of cover, become observed, and then strike. But with pounce they should be good to go.
Exploration mode and encounter mode are different, the minion trait has no real impact on exploration mode and as such it is up to the GM as to whether you would need a control animal roll to get your companion to be moving stealthily with you.
Personally I would wager most GMs would just let you determine what mode of action your companion takes during exploration mode.
Other than that, if it enters combat where it's stealth roll beat the perception DC of the foes then it is stealthed and they are flat footed, if not then not.