I use Signal as my only messaging app. If someone doesn't have Signal installed it will automagically fall back to unencrypted SMS and show this using an open lock symbol and a grey send button.
I used it without Google Play Services before, but now I just use Signal (Works with SMS too) and it also works without Play Services. Note that if your ROM includes Play Services and you used adb to uninstall it you'll need to reinstall and disable it to get through setup (Something about their detection logic is off).
I'm sure there are other OSS alternatives but this one just works for me.