> Adding a new type to a union? Breaking change. Adding a new element to an enum? Breaking change.

This is incorrect. I've personally gone from type X to union {X,Y} in C++, you just need to use the resolving decoder that takes both schemas. Enums can also be resolved based on names. Check out the schema evolution rules here:

See https://avro.apache.org/docs/current/spec.html#Schema+Resolu...

Of all the binary serialization formats of this ilk (proto, thrift, flatbuffers etc), Avro definitely has the most schema flexibility.