I'm quite surprised how many up-to-date applications can be installed via APK files or alternative markets (F-Droid) and work. For instance, thinking of Threema or Whatsapp, two continously maintained applications which do not inevitably depend on GApps.

How is the experience, though? Do you find that most mainstream apps run without issues? Or do you need to exclusively depend on one of the OSS app ecosystems like F-Droid?

Google tracks you via Play Services. And any Google application comes with Play. So if you're trying to get away from Google tracking, you have to get completely out of the eco system including Play Store. So yeah F-Droid (haven't used it) or what I just mentioned in another answer, Aptoide (haven't used it but searched for some common apps and found them).

Sure, I get that. But everything is a trade off. I'm probably not as concerned about the privacy issues inherent in Play & GSF, but I'm at least somewhat concerned. Just trying to figure out what exactly I'd be giving up, and in what ways I'd make my life more difficult. (Obviously that's a pretty me-specific thing, so I'm probably not gonna get a great answer here. But I think it's worth thinking about.)