I can't give you a firm answer (I'm writing this post off the top of my head), but if their phones can't use play services, you will have issues. A lot of apps depend on a bunch of Google Play Services APIs to work correctly, although there is an open source project to build a drop in replacement called microG but my understanding is that it isn't quite there yet. In general, yes you should expect usability issues if this is the case.

HOWEVER, some people (I'm not one of them though I see where they're coming from) who would regard these issues as a worthy trade off for keeping some distance from Google for privacy or whatever reasons. The subreddit that you'd want to start researching would be old.reddit.com/r/fossdroid if that sounds like a route you'd go down. If you use Linux full time, it would be something doable, but if that's not your thing I'd keep my distance.