As of right now, it's looking like GrapheneOS will be unaffected, and Google has yet to lock down the bootloader. So this should remain a valid option for at least 2 years.
Other than that:
- Any smartphones with an unlocked bootloader + any ROMs without gapps
- Chinese smartphones with non-Google Android builds
- Linux smartphones
- Bonus: Huawei is about to release their own non-Android OS, but I wouldn't expect it to be privacy-friendly
Honestly there probably isn't any good, long-term solution. Personally I'm somewhat shocked we've gone this many years with reasonably open smartphones. Next step is probably closing bootloaders in new laptops, as part of the switch to ARM (which is already undergoing).