Android devices could push something like https://gitlab.com/AuroraOSS/AuroraStore or even F-Droid to get a preinstalled store that's not completely evil.

For Linux devices, if you have a powerful enough phone (Pine64, can we please have a really beefy PinePhone?), you could bundle Waydroid + Aurora/F-Droid.