TLDR: I had to change the interface name from eth0 to eth1.
Full story:
So I had a bunch of slow starts just now. Some were also painfully show to shut down too. Probably been an issue for a while but I just didn't notice.
Anyway, in my case, I had a mix of containers which had
* no IPv6 address showing - slow to boot. Just over 2 minute delay from start to pingable... That's the clue it was a timeout.

* no IPv4 and no IPv6 - no idea if they were slow but obviously no networking at all

* IPv6 set to static with "none" showing a link local address (and some set to SLAAC with that working), and IPv4 working fine - I think these all booted up fast
I tried enabling SLAAC as others have suggested, but noticed no IPv6 address showed up still. This was true for both groups without IPv6 addresses. They still had no IPv6 (and no IPv4 for the ones in that group).
I then tried
changing the interface name from eth0 to eth1. Everything suddenly appeared. IPv4 and IPv6. I then changed back to eth0 and it stayed. I tried shutting down one of the containers that previously was very slow to start, and it was now just 2 or 3 seconds.
Many of my containers date back to around late 2010. I started with PVE 1.6, and most of the core containers were built back then on OpenVZ and eventually migrated to LXC. I suspect this is part of the issue. Maybe old configs on the containers (all debian) have some references to the interface that block Proxmox either from trying or from making changes. Changing the interface name perhaps allows proxmox to recreate the whole config or something, either it's own or the one inside the container... I don't know LOL
Edit: Sigh... Just noticed one of the containers running Samba had not loaded Samba, so I rebooted it. It got stuck shutting down, then when I forced it off and back on, networking failed to load again. This time I've left the interface name changed to see if that helps. But I have doubts now.