I see the same problem with macOS High Sierra 10.13.3 on a MacBook Pro (15-inch, 2017). Even Apple's Bluetooth Explorer app (part of Hardware IO Tools) shows the same problem.
Some peripherals are affected more than others. Apple TV always seems to show up very quickly while other peripherals are slower or don't show up at all.
See the related question is answered here:
CoreBluetooth advertising detection time
where apparently CoreBluetooth is not listening continuously and shares an antenna and resources with Wi-Fi and regular Bluetooth. I originally thought that turning off BOTH Wi-Fi AND "Handoff" improved the ability to see advertisements as well as shortening the time to connect. "Handoff" is turned off in Apple - System Preferences - General by unchecking "Allow Handoff between this Mac and your iCloud devices", but this may not be true.
Note that the problem does not show up in iOS, possibly due to better BT and Wi-Fi co-existence support and between Handoff (Airdrop) and regular BLE usage. The issue appears to only be one of the proportion of BLE listening time during scan and connect. Once a connection is established, there does not appear to be as much interference. In part, this is due to the fact that after one connects there are automatic low-level BLE retries and frequency hopping between fixed-in-time connection intervals. During scanning and establishing a connection (both of which rely on seeing advertising packets) one sequentially rotates through the 3 BLE advertising channels on each scanInterval. Technically, the advertising channels do not overlap with Wi-Fi (see http://www.argenox.com/a-ble-advertising-primer/).
[EDITED FOR NEWER INFO] After more extensive testing it appears that the problem with macOS may not be so much interference from Wi-Fi or Handoff, but rather having scanWindow and scanInterval settings that behave more like how iOS works in the background. Since for some peripherals it sometimes takes up to 1.5 minutes to be found, a 30/300 ratio with 1 second advertising and up to 10 ms random shift (so figure 5 ms as an average shift) could take (300-30)/5 = 54 intervals (seconds) to get detected if the peripheral is not following Apple's advertising interval guidelines that are intentionally away from 300 ms multiples and with some bad luck on the random shifts could be somewhat longer, which is roughly what seems to be seen. Unfortunately, I have not found a way to force macOS to use a higher scanWindow/scanInterval ratio similar to iOS foreground.
[SECOND EDIT ADDITIONAL INFO] If one follows Apple's advertising time of 1022.5 ms in the peripheral, then even with iOS background or with macOS 30 ms scanWindow and 300 ms scanInterval, the median time is roughly 5 seconds while the maximum is around 19 seconds so could be somewhat longer with very bad luck of the 0-10 ms random shifts.