@aral the "install another OS" also has the issue of that OS needing to exist in the first place, and usually it doesn't for quite a while because turns out making Android ROMs isn't exactly that trivial
i think for that to hold any merit as a solution, at the very least the phone manufacturer should provide a base OS image without gapps on it
personally i think a reasonable middle ground would be the phone asking whether to install them in the initial setup process though