Macfinger, I'm 101% with you on this; all you said makes perfect sense and it's a perfect recap of the problem.
Since we're on the topic of devices, I'll gladly list my hardware again.
I have a Sony DSX-A410BT I bought in December 2019, which I updated to the latest firmware on day one. The firmware was released in February 2019; I guess my unit had been sitting on a shelf for a while before I got it. It does support Siri Eyes Free, but this is where it gets odd: until iOS 13.4, Siri Eyes Free was only triggered by the stereo itself, i.e. if I long-pressed the knob. If I called up Siri with my voice, it would work as normal, showing my speech as I spoke and doing everything.
(I distinctly recall it being that way, because I have Siri in Italian and it consistently misunderstands anything not in Italian. Peeking at the screen allowed me to get an idea of whether it had understood me or not before having to wait for the spoken reply.)
After 13.5, the Siri Eyes Free interface shows up at all times, even if I call Siri up with my voice. I am still able to play music — misunderstandings aside — as I have an iTunes Match subscription so I use the default Music app. However, my personal pet peeve is that I use Waze for navigation because Apple Maps is mediocre at best in my area, and Waze's own UI and speech recognition are arguably pretty bad. Before, I could say "Hey Siri, directions to Whatever Road using Waze" and it would work. Now I get the dreaded "can't do it while you're driving" message. Coupled with (again) Waze's bad UI and speech recognition, it makes setting a destination on the go a complicated ordeal. Either I pull over and do it, or do it while driving. One's inconvenient, the other's literally dangerous.
Note that, following someone's suggestion here (I can't recall whose, I apologize), this did start working for me for a while. I disabled and re-enabled Bluetooth from the Settings, and for a while it worked. Note that I did not unpair and re-pair the car stereo, I just disabled BT and enabled it again, then reconnected the phone to the car stereo. It worked that time, but it's been spotty ever since and I honestly don't have the patience to do this dance every single time I get in the car. Even if I remember to, it's just a waste of time for something that's clearly a bug and should be addressed by Apple. I don't know if it helped because in that case it was the phone looking for the stereo rather than vice versa, as it normally does.
I also tried all Bluetooth speakers I could get my hands on, just to see if I could reproduce the problem with them, but none seems to be affected. I'm not sure if car stereos identify themselves as such, but it makes sense that they do. My Sony does show extra settings in the "info" screen in the Bluetooth settings on the phone (whether to sync contacts or not), but disabling that makes no difference.