There are a lot of really good free software Android apps, like, almost enough to have a usable phone with only free software.

I use
- Firefox as my browser
- Signal for messaging
- VLC to play media
- OSM for maps
- Twidere for twitter.

I still need (feel free to suggest one!)
- a camera with nice filters (I use B612)
- a fast and good UX wrapper around the nextbus API (I use the Transit app)
- email, calendar, etc... but my accounts are with google, so, meh

@morganastra if you think you could handle a phone without google, check out copperhead os. it's hardened android and as open source as possible, with no google services.