How common is finding an egg while exploring?

that's not extremely rare but it's not that common most of the area have a good the chances to make apear an egg tho in some places their ''parent'' may stop you to collect it. The area who let you see the egg before the encounter (like the festival zone) have less chance to make them apear

@Cian

How common is it to find pets to keep without battling, and not eggs?

You cannot find non-egg pets that you can just 'take with you' in the same manner in the wild.

To gain new pets without battling...
a) Buying from other players
b) Making pets with Essences
c) Buying from the Ny'vene and Puffadore shops in the third region
d) Holding one of the top five places on a Species Nurturing Board during a Seasonal Festival (no wait, that's an eggling you get for that)
e) [I'm sure there was something else, but we can't think of it right now]

yes there is something else it's called breeding

We specifically didn't mention the scale shop and breeding because those are ways of obtaining eggs that will later grow up to be pets.
"to find pets to keep... and not eggs"...

... Although I suppose that nurture boards gives an eggling. Trying to separate two distinctly is hard when you're used to just thinking of them as a single topic.

... e) get picked in an official Forum Game involving pet creation (although it's d, I guess, if we exclude the nurture board? Oh whatever)
?) Contests and giveaways in the Games, Contests, and Giveaways forum

There is one way you can find pets just wandering around. Sometimes when it says "You see something moving up ahead", the something turns out to be a hatchling that you can keep. It seems pretty uncommon, though; I've only found two or three that way so far (I've been playing for about a year but I took a long break). Usually you just get mobbed by enemies. :p