If your machines rely on the network to determine their hostnames, and Puppet is configured to use the hostname as certname (as it is by default), then it follows that you cannot successfully perform Puppet catalog runs until the network is up and the machine has determined (or maybe just can determine) its own hostname. I'm not well versed in OS X service management, which in any case I understand has changed somewhat over time, but surely it has a conventional idiom for expressing that sort of dependency.
Alternatively, and perhaps a bit quicker and dirtier, you could run the agent via an external scheduler instead of as a daemon in its own right (i.e. with --onetime --no-daemonize). This has a lot of advantages, one of the lesser being that if the agent does issue a certificate request, it will do so only once per scheduled run (and fail the run if it does not receive the requested cert). Supposing that you can rely on the network eventually coming up, and the machines learning their correct hostnames, the problem will go away (on a per-machine, per-boot basis) once that happens. Overall, you will see far fewer cert-request errors logged.
John