I use LineageOS+microG and practically all apps not made by Google (WhatsApp, Spotify, PayTM) work as they should. Even for some Google apps, there are good alternatives like YouTube Vanced etc.
That doesn't sound right.
FAQ on using LineageOS with a locked bootloader: https://www.reddit.com/r/LineageOS/comments/n7yo7u/a_discuss...
Some Android distros, including CalyxOS, are only intended to be used with a locked bootloader, and support over-the-air upgrades without needing it to be unlocked.