I believe Google Play does actually have the ability to remove apps if it wants to, intended for malware.

If the government were to mandate that they use that feature, or Apple use that feature, especially to prevent future side-loaded installs, I'd be much more sympathetic to the overreach arguments. But that's not what they did. Rather this is a narrow law that prevents these companies from assisting in wide scale espionage. The fact that they could do some other bad thing doesn't mean the thing they did is bad.

The courts use phrases like "narrowly tailored to achieve the governments legitimate interest" to describe the balancing test here...