Sure, the situation on mobile devices is actually rather worse. It's pretty much Apple, Google or Microsoft. With Android at least, it's possible to run a version that comes without anything google. There are alternative app stores, including one built around the idea of free and open-source. It's not ideal, but works surprisingly well. Fortunately, the situation looks a lot better on the pc side.
Yeah I know, I'm using f-droid, but it's pretty lacking in selection (not really their fault, but there is a fair share of open source apps that are on play store and github but not on f-droid). I'm currrently getting half of my applications from the play store, but not through the play store (*puts on the tinfoil hat* I don't have an account), I sideload the play store APKs. Sometimes I download the compiled APKs from XDA or github, if they're available there. Very small percentage of my apps are from F-Droid.
Yes, it really isn't all that easy, unfortunately. I pretty much handle it the same as you do, although sideloading apks comes with its own share of potential problems and we really need to watch what we're installing that way. Simply grabbing them from the playstore is one of the better options, but of course not always an option (since the DRM stuff the apps are looking for isn't on the phone.) At the end of the day, what goes for the computer goes for the smartphone x 10: Consider everything done on it at least potentially publicly available or worse.