Since 2019 the landscape has deffinitely changed. "Hardcore" Free Software phones like Pinephone, Librem or PostmarketOS are still difficult but if LineageOS is Free-Software-enough for you, don't give up now. There is grapheneOS that should be no-compromises solution with it's sandboxed google apps. (Haven't used it myself.) MicroG now passes safetynet once again and is pretty stable. (Altrough on some phones you may need root to make it believe that the phone is not rooted.) Clean LineageOS without gapps is more usable than ever due to the huawei-google breakup resulting in a lot more apps being published on huawei appgallery without google safetynet requirement. (Unlike their playstore version.) Downloading apk from Appgallery website requires just some url manipulation for which you can use following bookmarklet:
javascript:(function() {window.location=window.location.href.replace(/^https:\/\/appgallery\.huawei\.com\/app/g, "https://appgallery.cloud.huawei.com/appdl" );})()
Source: me. I daily-drive 7 year old phone running LineageOS with almost no issues. I also have a backup phone where I multi-boot LineageOS+MicroG and postmarketOS for fun and experimentation.