It's foolish to think open source isn't possible on Android.
0. Introduction
I was a fool myself, I thought the apps my phone's vendor made were simply too aesthetically pleasing to switch from. I thought there were barely any good libre apps, and they were all limited in functionality compared to their closed source alternatives. I was ignorant to the fact that the apps I was using were filled to the brim with corporation branding, useless features, and bugs (which I thought were acceptible for some reason). But I digress, I'm here to show that there is a world where you install only libre software and still use your phone to do whatever you'd like. I needed this years ago, so I'll take you on a journey down the rabbit hole to prove it.
Assuming you already have some idea why libre software is preferable, the first step is embracing minimalism. Of course, you will not find open source versions of the exact same proprietary apps you love and use on a daily basis. Though, an open source alternative will aways exist in some form. If you embrace minimalism and identify what you want from an app with precision, you won't be carried away with extra featues that may simply be bloat.
Disclaimer: Some of the open source communities may be nasty, but at least they don't hide their dirt.
1. Basic phone features
You need to replace your default system apps. You didn't choose to install them, you were fed those apps. Just because the vendor doesn't want you to replace them doesn't mean you have to keep using them. Root your phone (Why is it dangerous and letting a company you know nothing about have control over your device and data isn't?) and delete those apps.
Phone app (Dialer): Go ahead and install Koler or Simple Dialer. NoPhoneSpam can be used to block based on patterns. Call Recorder can be used to record your calls, use Call Recorder - Skvalex (closed source) with its Magisk module if it doesn't work. Use Share my number if you need to share your number with a QR code.
Gallery: SimpleGallery has an all albums view in addition to per album view. It can remove metadata, filter media, has a recycle bin support, and allows basic editing.
Files (browser/explorer/manager): Are you, by any chance, still using Root Explorer? Perhaps your vendor's modern files app? You could also be dependent on Google and using Files by Google. Maybe ES File Manager and its ads had an impact on you. No matter which one you use, Material Files welcomes you. It has everything you need. If you can't give up your files app because it cleans junk files / optimizes or speeds up your 256 GB phone with 8 GB of memory, know that you don't need any of it. If you're used to the 2 panel layout, remember minimalism. You don't need it, this app has multi-window support.
Messaging: QKSMS or Simple SMS Messenger, the former should be superior to the default messaging app. If you can get a friend to read this post, you can use Silence (not to be confused with Silence the call blocker) to converse with them encrypted.
Software catalogue app: Droid-ify for open source apps and Aurora Store for apps on Play Store only. You can log in to download the apps you've paid for.
Launcher: Stop using a Google launcher, Nova Launcher, or OneUI's launcher. Yes, you can do without a Google search, weather, cpu temperature, and free space widgets (though you can still find them in libre launchers). There are a lot of open source launchers, though Olauncher (for elegant simplicity), KISS Launcher (power users), Discreet Launcher and Omega Launcher (more familiar) are some of the highlights. It's fun trying out new launchers, don't be afraid: F-Droid is your playground.
Voice Recorder: There are decent open source voice recorders but the proprietary ones are way better, no doubt. You can still live without editing voice recordings though, install Audio Recorder (not to be confused with Audio Recorder), it allows you to go back a few seconds and record over. Check out RingDroid if you want to trim an audio file.
Clock: Yes, even the default clock app can be changed, so why not? Try Clock (the new version).
Camera: Open Camera is worth a try. If not, stick with what works best for your use case. Keep in mind minimalism, though. Don't take a photo unless you really want/need to and consider using a simpler camera app in case you don't need filters or anything like that.
Browser: It might sound surprising but this is the easiest part. If you're using Chrome, install Bromite. If you like Firefox, install Mull. There are some simpler browsers that run on WebView, you can test them out if you want. For syncing bookmarks, use xBrowserSync.
Music: Newpipe (casual), Seeker (hq) to save locally. Vanilla to play local music. Blade if you're paying Spotify or want Deezer's library. Spotube works as a Spotify client. ViMusic is a simple player that can play from Youtube Music.
2. Social media
Don't use it. If you must, Frost for Facebook, Fritter for Twitter, Infinity for Reddit, Newpipe for Youtube, NewPipe x SponsorBlock for Youtube with SponsorBlock support (NewPipe's developers refused to implement it), Clipious as an Invidious client (you can use it to read replies to Youtube comments and proxy videos through Invidious), Xtra for Twitch, GIider for Hacker News, Jerboa for lemmy (the only working Lemmy client on Android so far). Use Matrix bridges for Discord and Telegram servers, SchildiChat and Element are two popular clients.
Google Drive: RCX to access your files on Google Drive, Onecloud, Dropbox, Amazon Cloud. See also Round Sync, an actively maintained fork of it. Any self-hosted solution like Nextcloud will still be better.
Google Translate: SimplyTranslate Mobile uses Google Translate, so the translation is decent. Monocles Translator if you want to go all libre and use LibreTranslate, which has mediocre translations. InstaLate for seamless LibreTranslation with an overlay.
Snapspeed: Litrato comes close depending on what you want to do. There's also Phimp.me, which can edit images but it is far from a polished app. Don't use an image editing app, try Litrato and Phimp(dot)me if you must, go with Snapspeed if you really need those features. You can use Simple Gallery's built-in editor or Imagepipe If what you need boils down to filters, cropping, rotating, sketching; Pocket Paint also works as it has layer support, you can get creative with it.
Google Authenticator: Aegis is just better. If you need MOTP, use andOTP which is larger in size.
Google Photos: Self-host a Piwigo, PhotoPrism, or an Immich server. Better yet, embrace minimalism and don't have thousands of images in your gallery. Frequently organize and delete unnecessary images.
GBoard: FlorisBoard as it has detailed custom themes. FlorisBoard already has a clipboard. You can also try XClipper if you're not satisfied.
Google Keep: This app is so basic that most open source note taking apps should suffice. As for the top editors, Joplin is good, can sync pretty well and even has error correction tools in case sync goes wrong, but you can't attach files bigger than 10 MB to notes. Neutrinote CE is almost just as good, it even has basic sketching feature but you can't attach anything other than images. It also doesn't offer anything to organize or group your notes that works with other apps. Markor has terrible UX but it has good attachment support. Quillpad is the closest in UI to Google Keep. It has an enjoyable UX and live markdown processing. Unfortunately, you can attach only images in-line, and you have to manually put in the whole path to the image as though you're on PC. Notesnook was added to F-Droid recently. It has clients on all major platforms and it might be the most modern libre notes app. Though, it has several features (some vital depending on the use case) locked behind a paid subscription.
Google Docs/Slides/Sheets: OpenOffice Document Reader can read and edit, but don't expect much. Collabora Office is a way better editor, it works but doesn't have as many features as Google Docs does. Neither of these options offer collaboration. Padland has collab through Etherpad but it's well-known how hard it is to get everyone you are working with to switch to another app.
Google Assistant: Dicio is already on F-Droid but it won't get what you are saying. Possible actions are limited. There's also Athena that's in development, though it is not ready for any kind of use. Depending on whether you need some sort of an accessibility service, you can get away with ditching Ok Google / Alexa / Cortana / Bixby. TalkBack should help with it too.
Google News: No alternatives. Unless it has to do with your job, it's a stressful form of entertainment, drop it. News Provider can get news from rss feeds though. Thud has a lot of feeds set up by default, but it is laggy. Read You offers the smoothest RSS experience I've had on Android.
Google Tasks: Tasks.org is easily the best tasks app out there. It doesn't have smart language recognition or quick add, but it's still great. It's comparable to Todoist and TickTick.
Google Maps: Organic Maps (based on OpenStreetMaps) can suffice. You probably think an offline map would just suck and you can't do anything with it, but it works pretty well. It has add-ons that can report traffic jams. Your biggest issue will be the lack of places (with user comments and additional information), for which you will have to use GMaps WV, a wrapper for Google Maps.
Wallpapers: Olauncher has a new wallpaper every day. Cardboard Museum changes your wallpaper periodically with a different one from Danbooru. There is Muzei, which offers a new wallpaper every day. Doodle has several wallpapers and offers some customization. Resplash is like Google Wallpapers in how it pulls from a large online database, it is basically an Unsplash client. If you don't like any of these apps, browse the internet; don't use the the spyware that is Zedge.
Digital Wellbeing: UsageDirect can display your screen time per app. DetoxDroid can make your screen grayscale (per app) and break infinite scrolling. With OpenTimeLimit, you can limit an app's usage for a user. TimeLimit.io can be used for multi device support either self-hosted or with monthly subscription.
Speech Services by Google: RHVoice offers TTS. No open source STT that works for the English language is available on Android (Dicio, barely).
4. Oddly specific alternatives
Samsung SoundAssistant: Audio HeadQuarter works the same way with its Magisk module, is also way more customizable. At least some parts of it are not open source, however.
Goodreads: Badreads or Openreads with no community reviews. Embrace offline apps.
Trakt: Episodes for series (still needs some work for an enjoyable experience). Nekome can be used for anime and manga if you trust Kitsu. CineLog and Movie DB can both act as a database where you save movies or look up other movies, but they aren't actively developed and lack organization features. This is where SeriesGuide comes into play. It can be found on Izzy's repository and it "tracks or reports your" activity but it can help you group and organize your series and movies. It has premium features (extra) that require a monthly subscription. There is also an alternative called Showly.
Any streaming app (Hulu, Netflix...): Cloudstream-3. See CS3 Docs to learn to set up the app and install the repositories you want.
VPN: Depends on the provider. CalyxVPN is free, Mullvad is paid. Both have open source apps.
Spotlight-like: Blue Line Console, can be used alongside your favorite launcher as an assistant app. It can do basic math and unit conversions, supports widgets. It's addictive.
WinDirStat: DiskUsage does not have a list but it offers a visual block view that can clearly show what's eating up all the space on your phone.
Github: OctoDroid, very slow development but it's still good. It doesn't support Github Discussions and the new issue forms yet.
CamScanner, Office Lens: OpenScan will get you covered. Don't use the 155 MB spyware CamScanner.
Forest, Flip (Productivity / Pomodoro Timer): Goodtime is perfect, you can use it with your phone's screen locked.
Moon Reader: Librera Reader is just as good, if not better.
Adobe Acrobat Reader (PDF read and annotate): Librera Reader.
Sketchbook: Saber for basic sketching. Krita is a great app that works properly only on tablets. Another option is Pocket Paint, which is barely okay. PxerStudio is great for pixel art.
Your Phone Companion: Zorin Connect, KDE Connect, Device Connect all do the same thing. Share To Computer is the simplest wireless way to transfer files or text from phone to computer, as it doesn't ask for an internet connection, it's handled locally.
Whatsapp: Jami has come a long way, use it if you have people who'd be interested in a libre P2P Whatsapp alternative that doesn't require any signup or phone number. XMPP/Jabber is also an option as long as you can host a server yourself. If not, then use Signal, if that still doesn't work for you, no alternatives. You can use Whatsapp Web To Go, it should work without the Whatsapp app. Try Open In Whatsapp if you need to text people not in your contacts.
Vocabulary(dot)com, Knudge(dot)me: No alternatives. If you aren't preparing for a test, don't bother with these and just consume media.
MyFitnessPal: Waistline is the only app that comes close but has only packaged products, so you can't use it if you don't consume a lot of packaged food.
Squid, Nebo (Handwritten notes): Xournal++ Mobile is not fun to use, but it is free software. Saber is a new alternative.
Remote for Samsung TV (old smart TVs): Sam Remote uses Wi-fi, so there is no need for infrared. The app doesn't have play/pause buttons.
VirtualTablet: Weylus can mirror the screen to the client. GfxTablet can also be used, though it has no mirroring.
AccuBattery: BBS can be used to track what's draining your battery. AccA with its Magisk module is a must-have as it will help your battery last longer.
Any fitness app (Thenx, Sweat...): Feeel for a workout database and how to do exercises. Wger too has a database of workouts. Workout Time! has predefined workouts as well and it offers a timer, which helps if you have issues with resting too much. GymRoutines is a simple workout app, you can make your own routines. There are just so many apps with unique featues in the open source scene, just try them out.
QR/Barcode Scanner: Binary Eye, no doubt. This app can zoom, crop, use the flashlight, scan images from the gallery, use both back/front cameras, have history, create barcodes.
Calculator: You don't notice how infrequently you use your calculator app until you delete it. For simple calculations, Blue Line Console can act as the most unobtrusive calculator. For complex calculations, try num++ or MicroMathematics Plus (plots, graphs). If you happen to make simple calculations frequently, there's Calculator Notification. Calculator++ is a good app with interesting gestures, a widget and a window mode.
Ad blocker: AdAway edits the hosts file to block ads.
Reminder: SimpleReminder is almost feature-complete now.
Metadata eraser: Prefer Imagepipe (over ScrambledExif, this one opens the share menu automatically instead of saving the image) for quickly cropping, scaling, and sharing images because it is lighter and still has more features. ExifEraser to erase metadata of all images in a directory. Simple Gallery can also remove metadata from multiple images.
Sync: Syncthing is a godsend, you can use it to sync your notes, images, music, any kind of library and archive P2P in your local network. Use WireGuard and sync from anywhere in the world.
Firewall: AFWall+ allows apps to access wifi/mobile/vpn/lan. Can't do without it.
Package manager (and the likes of SD Maid): De-Bloater to use custom scripts that can delete tens of apps at once, and restore deleted apps in case something goes wrong with its Magisk module. App Manager is an all-in-one tool that can block activities, permissions, control app ops, check app directories, disable modules, and so much more. It's powerful and you probably need it.
Text editor: Editor by the amazing billthefarmer, master of lightweight apps.
Video player: mpv's UX is better than VLC and it doesn't try to be everything at once. It's just a video player, and it can play network streams.
Root: Magisk because why wouldn't you want to root your phone? It's systemless, has modules support that renders Xposed obsolete, and it is open source unlike SuperSu.
Search inside files: aGrep takes a string and a directory as input. It searches for the former inside the files found in the latter.
6. Quality of life
Image Viewer: ImgurViewer (can see images/videos from a lot of websites), so you don't have to open media links in your browser.
Link manager: URLCheck will make it much easier to deal with links as it allows you to view the full link before opening it, choose an app to open the link with, copy/share the link, and clean the link (delete unnecessary parameters that track you).
Image upload: Pomfshare can upload your images to Pomf(dot)cat, Sicp, Uguu, one by one, not as an album. When it works depends on the servers.
Redirecting: UntrackMe redirects to open source frontends: Youtube to Invidious instances, Twitter to Nitter, Reddit to Teddit, Instagram to BIbliogram, Medium to Scribe, Wikipedia to Wikiless, Google Maps to OpenStreetMaps.
Share to save: SaveTo saves files via sharing, you can use its companion app SaveTo.Downloader.
Showing an image: Secure Photo Viewer is great if you happen to show an image to someone else.
2FA ease of use: BluePass syncs your 2FA codes sent via SMS with your PC.
Quick music player: Dialog Music Player is useful when you want to listen to an audio file in your files app.
Password manager: KeePassDX is one of the best password managers out there.
Blue light filter: With RedMoon, you can adjust the color temperature, dim level and intensity level of the filter. It makes it easier to use your phone at night.
File Encryption: Secret Space Encryptor encrypts files or folders. DroidFS, creates encrypted volumes that are easy to access.
Battery saver: SaverTuner is not a battery saver, rather it allows you to configure Android's builtin battery saver better.
Terminal Emulator: Lightweight terminal, better than the default one with multiple window and special keys support. Termux is a powerful terminal emulator.
Video Transcoder: Simple video editor and transcoder. Use ffmpeg on Termux for faster and more accurate results. VideoCrop allows you to resize and crop videos, output is up to 20 seconds.
Kotatsu: Download and read manga, 40 MB smaller than Tachiyomi.
MyExpenses: A solid expense and debt tracking app where you add your transactions manually. There are lots of apps like this on F-Droid, check them out and pick whichever you think is the best.
Decisions: Making better decisions. I wish I learned of this app sooner.
LM videodownloader: Download videos you come across on the web, pretty useful when you don't have a direct link to a video. Use YTDLnis on websites supported by yt-dlp, Seal freezes during some batch operations.
Photok: Image vault. Encrypt your images and view them conveniently.
Currencies: Quickly convert currencies, it allows you to favorite frequently used ones.
Monocles chat: is an XMPP/Jabber client. You can join group chats and send direct messages to other users, you can think of it as federated Whatsapp. Monocles isn't very stable but it makes the chatting experience much better by merging messages sent by the same user under just one avatar unlike Cheogram, another XMPP client that is more stable but has less features. Both are forked from Conversations, which has no themes with pitch black background.
FFShare: It pipes multimedia through ffmpeg to compress them before sharing.
Privacy Indicators: An icon pops up when camera/microphone/location service is in use.
Image Toolbox: It is the best libre app to resize images. It supports batch resizing too.
SuperTuxKart: One of the best video games on Android. It's a racing game that also works on Linux, has singleplayer and multiplayer modes. You can even play soccer with karts.
9. Apps tightly tied to a service
Banking apps and shopping apps have no alternatives, you don't have to use them for the most part as they work in browsers. Do it in a work profile through Shelter if you need these apps.
10. Magisk modules
AudioHQ module is required to use Audio Headquarters.
Webview Manager allows you to replace the webview installed on your phone with Bromite or Ungoogled Chromium's webviews (or a custom one if you wish). The webview installed can be updated through an F-Droid app, they are updated also when you update the module.
MagiskHidePropsConfig can be used to change your device's fingerprint and pass the SafetyNet test. You may need this app if you want to run banking apps.
Call Recorder - SKVALEX is the module needed to record calls using the closed source call recording app.
11. ROM
Arguably the most drastic change. Go to your device's Xda forum page and pick a rom for yourself. Don't be fooled by the number of options, almost all are based on AOSP, LineageOS, or GrapheneOS. If the rom has a different name than these three, then it has further customizations, which can be a great thing, though make sure it's not bloated.
GrapheneOS is the first recommendation. DivestOS is the second one, followed by LineageOS.
When you go down the rabbit hole, you become part of the Android open source community and a supporter of the free software movement in a way. You may donate to developers, share the idea with masses through word-of-mouth, moderate communities focused on FOSS, be a number in the # of times an app has been downloaded, or write about it to spread the idea further like I did with this post. Using libre software also allows you to communicate with the developers, contribute to their apps, and have an impact on the development of the apps you love. This is incomparable to Play Store reviews or telemetry.
I would have never imagined writing 3000 words promoting free sofware on New Year's Day if it wasn't for F-Droid and the community itself. Thank you.