All of this above. The biggest contributing factor though is that the radio will be off for 99% or more of the time when not actively sending, in order to save energy. This means you also need to wait for that <1% beacon/listening window to connect. And it’s not unlikely that you get interference / a bad transmission just at that time, so double or triple the wait time.
Or in short: It’s caused by saving energy and interference.
This makes sense for idle devices, but say airpods know they have been opened (or other bluetooth headset can be actively listening for a few seconds after power up), and on the other device you explicitely click connect on already discovered divice. I also don't understand why these connections are not 1ms even for devices which were not paired previously.
You can have a device listening only 1% of the time while only waiting a millisecond. Just listen for 10 microseconds and energy-save for 1 millisecond. Why aren’t they doing that?
Or in short: It’s caused by saving energy and interference.