My wired connection has only required a phone reboot once in all this time, probably due to bootup issue with phone and car not syncing simultaneously. I rarely charge the phone at home since the car now does it.
If android try a free music program called pulsar. My music is in alpha folders on the phone 64G sd card, if your mp3s have album, artist and genre filled in you can search for those, or I just make various playlists for various moods on the laptop and select them from the list on the car screen, and select random.