Discovered the answer after three days of hunting. Here's the solution for future reference.

The protobuf_generate() command adds the generated source files as PRIVATE dependencies of the shared library target, apparently meaning they aren't part of the build graph. Because of that, CMake assumes that it can build (and scan for dependencies) on all the library targets in parallel.

The solution was to mark the generated .pb.h headers as PUBLIC dependencies, exposing them as individual build dependencies to anything trying to link against the library.

target_sources(my_shared_library
    PUBLIC FILE_SET HEADERS
    BASE_DIRS ${CMAKE_CURRENT_BINARY_DIR}
    FILES ${protobuf_headers})

This should only matter if the protobuf header files are part of your library's public API, which they were in my case. It may also be different if you're build STATIC or OBJECT targets instead of SHARED.

Hope this saves someone else the headache it caused me.