> Now that I've looked at all of this and read about APT::Machine-ID, we'll probably set it to a single value across all of our fleet
This is not a good idea, the machine ID is supposed to be unique and shouldn't change over the lifetime - a handful of software relies on this property and it's the best identifier for an installation if you can't rely on hostnames.