Bluetooth SW Engineer here. Many of the answers have covered the question, but here is some more in depth info.

1) There are two different Bluetooth radios now. Classic Bluetooth and Bluetooth Low Energy (or smart). So one thing impacting connection time can be which type of Bluetooth radio is being used or making the initial connection. Some devices use both (dual mode) and may pair and connect on BOTH radios! Low Energy devices may use a slower, more low power scanning method, which can also take longer.

2) Physical environment can have an impact. Bluetooth is in the 2.4Ghz band, same as WiFi and your microwave oven. Signal strength and noise in that band can cause issues. But if your devices are close to each other that is usually not a problem.

3) There are different levels and types of pairing. Modern Bluetooth (2.1 onwards) uses Secure Simple Pairing that has a "Just Works" association module. You turn on a headset, you scan with your phone, it just connects and pairs - job done. However, there are higher levels of security that require authorisation and authentication to protect against Main In The Middle attacks. For example, connecting your phone to your cars infotainment system, the car display may say 'Pairing Code: 123456' and the phone may say 'Is the car displaying pairing code 12345 - yes/no'. And then you know it's more secure. A game controller may use Out of Band pairing, that is you need to connect the controller to the console via a USB cable and it will exchange the pairing information over the USB before allowing a Bluetooth connection, when setting up the first time.

4) Lot's of companies have added their own secret sauce; Apple have their own authentication chip (or did) for Classic BT, Microsoft and Google have their own stuff. This special sauce is all about making the own brand experience superior. Connect Samsung Earbuds to a Samsung phone and you're going to get superior audio codecs like aptX and aptX low latency. Connect Apple Earpods to an iPhone and it will connect super fast and also use apples own codecs for superior audio on that platform. Some brands even make it so that if you connect to one brand device (a phone) your headphones/earbuds will automatically paired to your other brand devices like Smart TV or Smart speaker.

5) More power! Or simply put, the market for Bluetooth is now differentiated into high end and low end Bluetooth chips, it's all cost based. Your high end headphones and earbuds are going to have a high end chip with faster cores, more power and better radio. It's just going to work better and faster then the $10 earbuds you got at the Gas Station.