Almost all of our Android phones come with a modified Android OS that uses Google services. As you (probably) know, Google is not much of a privacy-respecting company to trust. I personally suggest deGoogled operating systems such as /e/ or LineageOS but if you can’t replace your Android phone OS with such operating systems, you can at least start using software libre apps on your phone and get rid of Google.
F-Droid is a community-maintained software repository for Android, similar to the Google Play store. The main repository, hosted by the project, contains only free libre software apps. Applications can be browsed and installed from the F-Droid website or client app without the need to register for an account.
I believe the best app store for software libre Android apps is F-Droid. You can download its APK file from their site. F-Droid supports many languages so if you want your app store in your language, you probably won’t have any problems.
You also don’t need to worry if the app you want isn’t on F-Droid. You can always find a free libre alternative app. For example, instead of GMail, you can use K-9 Mail (website – F-Droid) which are compatible with OpenKeychain (website – F-Droid) for encrypting your messages. Even if you don’t want K-9 Mail, you can have many other libre alternatives. There’s a libre software app for every need.
There’s even clients for Facebook Messenger if you still don’t want to leave it. i really suggest you to start using privacy-focused services but if you don’t want to, you still have libre clients to use with F-Droid.