Apps OP mentions as not working do not require Gservices. I have never had them installed and have TOR, NewPipe and more and they all function perfectly fine.
I suspect this is a network issue. (By not working you mean not connecting to the internet? And not other issues, such as crashing?) Perhaps try connecting without Orbot. Beyond that, fiddle with settings that pertain to connectivity. DNS resolvers also can cause grief, as an example.
I don't think the issue is GOS-related per se.
Also, a note: search here for FDroid (it is not an ideal option as there are security lapses.). Most will advise against its use.
And, what exactly do you mean by "the messaging app that it comes with also said it probably won't work on my new phone"? It's a most basic SMS app from 1800's, if anything should work on the phone 100℅ that's that app, lol. Or do you have a data-only plan?