Google Ads removed by uninstalling com.google.android.gms
As pointed out in comments, ads come from two sources -apps and targeted ads by Google

For the latter removing GMS Services doesn't help, rather creates problems as you discovered , since GMS


  Google Mobile Services (GMS) is a collection of Google applications and APIs that help support functionality across devices. These apps work together seamlessly to ensure your device provides a great user experience right out of the box


Better ways to get rid of apps :


Follow steps mentioned in Google support - not very effective
Sign out of ads when you set up your Google account
Use an ad-blocker app which takes care of ads from both sources. Adguard
is one good app if your device is not rooted. If it's rooted, your choice widens and is more effective


PS : I am not associated with Adguard but properly configured , it's great a way to get rid of apps and also have firewall

Also see this for more information Where is data of Google Play Services located in device? Can I safely delete it?