How do you deal with incompatible updates of the services?

I fail to see how they won't have the exact same problems.

Just like when developping an API, you build changes in backwards-compatible ways for the most part.

If you have to make a backwards-incompatible change, you probably need to make your service support two different API versions for a while, and hunt down services that are calling old stuff for a while.

This is basically how you can move forward on improvements without coupling "improve this microservice" to "update every single other microservice that is calling to it".

Though I believe part of the theory with microservices is that since you are working on such tiny surfaces, most services will never need to roll out a backwards incompatible change

You just roll back that one service and every other service picks up the change automatically.

Doing the same thing with shared libraries requires redeploying everything that is dependent on the bad library (i.e. hundreds of containers instead of two or three).

It's not necessarily that one model is better than the other just that using a hybrid approach often means having the issues of both with only a few (if any!) of the benefits.

You don't make incompatible updates, via adhering to service contracts. You can use protobuf or Avro as the schema for these service contracts and get varying levels of forward and backwards compatibility guarantees for schema changes.