I explored with all 20 of my unsorted pets, and didn't see a single Magic Shop. Not a one.

Also, is it just me or are the exp-giving buildings and scriptorium appearing a lot less, and the market appearing a lot more?

It's a balance update. 

We're also planning to reduce explore XP a bit because there's a significant disbalance in XP/energy ratio on islands and arena battles.

I noticed this too and I'm glad that magic shops don't show up as much since most of the time I don't want what they're selling (usually over-priced blueprints or invites; both of which can be obtained much cheaper via the auction house).

On the other hand, I think explore exp is fine as it is. I think battle exp needs to be buffed instead of nerfing explore exp; especially considering the fact that a lot of times my weaker pets will lose to the first mob they encounter which typically means they are trapped and can't do anything but challenge the mob that's 8 levels above them.

If explore exp is nerfed, I feel like the level range of mobs that can appear above your pet needs to be balance so that weaker pets still have a fighting chance. All it takes is for 1 important stat to be red to seriously gimp a pet's battling abilities and cause them to lose to mobs their own level, much less even stand a chance against 2, 3, 5 levels above. I understand you're trying to think of the future of the game when people have decendant of hero pets with amazing genes and they'll just stomp all over the battles in the game, but I think that a more dynamic approach should be taken to making the game more challenging for those pets when there are actually pets like that in the future.