Some obscure or secondary function might not work.

I had this app for example (can't remember the name) that insisted on getting networking permissions. I kept refusing each time it asked at startup time but it was working fine. Then one day I realized it wanted it for its online help that I never read.

It really depends on the app.

Also, you have app developers that copy/paste sample code, adapt it a bit to their purpose and call it good enough, even of the sample code includes a lot of libs and permissions that aren't actually used by that particular application.

Generally, notifications will no longer work, but most other functionality will. There is a good chance that if there is an ATM map, it will not work either because it requires Google Maps.

Yea common, I get a lot of those when not using gapps at all. Some possible longshot issue will trigger that message.

It's usually lying. I'd just long press it and hide the notification. If you have an app that's requires Google Play, and you absolutely have to have that app, then you can always make a second user profile and install play services into that. That way you can turn off play services when it's not needed.