I have Samsung Galaxy S9 running Android 10 with Android Auto built in and the original cable (also tried premium Belkin cable) and still couldn't get reliable connection. I agree all the variables in the Androidverse make for difficulties but I thought I should have been OK with that setup.
I have the Samsung Galaxy S10+ and, initially, Android Auto would not work for me.
In advance of taking delivery of the car I had purchased a USB A to USB A lead. along with an adaptor lead, USB A socket to USB C and Lightning plugs. (My thinking was that, although I have an Android phone my wife has an iPhone and therefore
should be able to use the same lead to run Apple CarPlay, clearly not at the same time as me running Android Auto!).
I plugged my phone in (using the USB C adaptor/connector, obviously) and, zilch! No amount of plugging/unplugging, starting Android Auto on the car, entering the Android Auto app on the phone would make any difference at all.
So, having read the various threads in the forum about this I decided to try a different cable, so ordered
this one. Plugged it into car and phone and Android Auto opened immediately, everything accessible and customisable!
So, for me certainly, it does seem, as others have clearly found, that the cable you use makes a whole lot of difference.