This doesn't always happen, but I'm pretty sure it only happens when devices are connected. In the attached dmesg, there's a USB keyboard attached (USB-C/Thunderbolt3 adapter to USB-A), and there's an external display attached (USB-C/Thunderbolt3 to HDMI to DVI) and there were connected from the get go not added later.
From the journal I'm not seeing any time correlation with boltd or fwupd but also fwupd doesn't seem to always print messages when it does things.
Based on the journal it's happening less than 1/2 the boots. And I see it has happened with kernel 4.16.6-302.fc28.x86_64, as well as 4.17.0-0.rc3.git4.1.fc29.x86_64.
Created attachment 275937 [details]
Created attachment 275939 [details]
journalctl -b -o short-monotonic
Matching boot for the previously attached dmesg.
See also multiple downstream bugs reports.
I'm adding Mika, but if this is still a problem, you might want to also email this problem report to email@example.com and firstname.lastname@example.org, since I don't know if the Thunderbolt folks pay attention to bugzilla.
Most probably this is due fwupd force powering off the Thunderbolt controller in the middle of initialization (sometimes initialization takes longer). Possible duplicate of https://bugzilla.kernel.org/show_bug.cgi?id=199631.