Even if you do this, on a standard Android device, there is still Google Play Services installed, which has every permission available on your device. You have to install a fresh custom ROM like LineageOS without GApps to avoid this.

Good point. You should install LineageOS first, you can then select the GApps bundle size you need or try and replace them with FOSS alternatives. For me, Yalp Store has made using LineageOS + minimal, permission sandboxed google services a bearable experience.