And WiFi automatically connected to your AP after that?
Exactly, and I tried again that (latest LE12 nightly on the card) still without wifi issue. And because last week I wanted to try the LE13 nightly, I still have it on a spare card. Using the LE13, I tried twice the same thing with power off then on, and no wifi issue. In the past, I had wifi issues: started the TV (the RPi it's always on), the LE asked for wifi password but didn't accepted or sometimes just started without wifi connected, after a reboot started without issue. Could be the same issue?
3B or 3B+? 3B uses a different WiFi chip (Broadcom BCM43438) than RPi3B+/RPi4 (both Cypress CYW43455). So that would also point to a driver-related issue.
Maybe yes, or maybe it's already fixed in the nightly builds whatever it was. If you don't have a spare card, you could make an LE backup, then update to latest LE12 nightly (because you can go back to LE12 stable if you will want it, the downgrade from LE13 not guaranteed) and try it...
Nope, definitely not the antenna, or it wouldn't be so reproducible. It's only after cold boot. Never after reboot. 100%. RPi is next to the AP.
If the RPi is next to your AP and you have any chance to use cable instead wifi, don't hesitate, change it. Far better speed, without issues. I have 3 RPi's with LE installed and at only one had wifi problems (no way to use cable in that place). The another two with cable connetion to my router, never had any network issue in the last years.