(edit: all of below stuff is only for not being on the same network. After that it gets ... messy)

Oh boy! First: Thank you - I thought to briefly validate my knowledge and understanding before answering and went down a rabbit hole :D this is my current grasp, happy to be corrected!

First: Most is actually not even distro agnostic but also OS agnostic:

Most modern wifi devices when you tell them to "connect to WiFi" radiates, literally, what it can do and what kind of connection it wants. E.g. im a wifi device with WPA3 capabilities and this is my Mac address to answer me.

OS specific is the question if your Mac address gets scrambled or not. For both iwd and networkmanager, which both support it, have it turned off by default. There is a big advantage to being able to be recognizable on friendly networks after all.

Now comes the part I wasn't aware:

Even your hostname is often still broadcasted publicly! This happens during the DHCP handshake - and many devices don't support apparently existing standards to address this gap. It's all about securing the first frames where devices align on communication standards, encryption way, etc. This seems to still be quite public.

Android was easier (and iOS seems to be the same but I didn't bother with that more): Same as Linux but more aggressive by default: Mac scrambling all the time while searching for networks ,DHCP uses obscure strings as hostnames, etc.

Fun fact: even those have stable max addresses once connected. Again, getting the same DHCP lease and being able to whitelist or recognized by the network seems to have more upsights than I was aware of.