Without being able to root, it's a challenge.
I've had Verizon Samsungs for years and dealt with this.
Start with the Universal Debloat Utility. . Note what it says about disabling some things isn't advisable. The recommended list is safe - I've used it extensively on Samsung.
After that, yea, something like RethinkDNS will help. I'd use it, but chose to run No Root Firewall to control network access (there are others, this is the one I'm familiar with). It acts as a VPN to provide the firewall functionality. You could then use another DNS provider that blocks ads and such (since ReThink also needs to run as a VPN).
I've disabled most factory apps, and several Google apps. You can disable Play Store and it'll work OK. If you disable Play Services you'll get error pop-ups frequently.
This is about the best you can do without being able to unlock the bootloader.
I'd start with a reset. Then setup the phone without a Google account, then run the debloater.
After that, do what you like.