Totally ungoogled you won't have the google service layer, if you still want to use some proprietary apps, it is possible but some won't work. The biggest constraint is often push notifications not working.
As an alternative you can use microg [1] which is a client side re-implementation of google services. Some part uses alternative service as backend, some will use google though, like push notifications.
Side loading can have its limitations has you need to find sources for APK that you can trust.
The best non google store is f-droid [2] in my opinion, all open source and build reproducible.
If you need some proprietary apps from google store, you can use the client Aurora Store [3] which still sources app from google play store.
In term of buying a phone with most of that, /e/ does sell phones with android + microg + their own store [4]
Otherwise plenty of phones allow to easily replace the operating system. You can look for phones supported by lineageos which comes with no google apps. [5]
[1] https://github.com/microg [2] https://f-droid.org/ [3] https://gitlab.com/AuroraOSS/AuroraStore [4] https://e.foundation/ [5] https://lineageos.org/