Comment 5 for bug 1734167

I think the primary issue is that cloud-init.service is depending on using the network fully.
cloud-init.service runs:
  After=networking.service
  After=systemd-networkd-wait-online.service
  Before=network-online.target

But systemd-resolved.service runs
 After=systemd-networkd.service network.target
 Before=network-online.target nss-lookup.target

I tried adding to cloud-init.service.
 After=systemd-resolved.service
but that did not help things.