I have a similar issue, with NetworkManager.service taking over 30 seconds to start, but it doesn't happen every time. Half of the time, NetworkManager.service only takes a few seconds to start.
I found this thread which most closely matches the behavior I'm seeing: https://forums.linuxmint.com/viewtopic.php?t=426864
However, I can't reproduce it every time, and I tried removing /usr/lib/systemd/system-generators/netplan but that had no impact on the issue (and "netplan generate" doesn't take more than a second to run). So I'm kind of at a loss.....