For rolling back 'Google Play Services', I think Chomorro is correct in saying that the Android Device Manager in Security Administrative needs to be disabled before you can remove the apk.
I did turned off USB debugging this morning and my microphone still works. That must mean that my microphone starting to work when I enabled that option is just coincidental. I will say though that my S4 almost instantly goes into AA mode when USB debugging is enabled vs the eternity, I'm impatient, it takes when it is disabled. I'm going to guess ~45sec to 90 secs with USB debugging disabled. I could be wrong.
So I tried a couple of things before I got my speech recognition to work. I don't know what did it, but again Chomorro may be onto something with which app is currently the "default app."
Some of the things I did before speech recognition started working are the following. I went into 'Application manager' and cleared defaults for 'Android Auto' and 'S Voice.' Then I connected my phone to the radio and checked for voice recognition.
I also enabled 'hands free mode' and try connecting my phone to the radio. I then disabled 'hands free mode' and connected my phone to the radio. I may have also gone back into 'Application Manager' and cleared defaults on those two previously mentioned apps again.
Then I enabled 'USB debugging' in the 'developer options' menu and chose 'Forget All cars' in the 'Android Auto' app. Between some of these steps when I plugged my phone in to the HU, my phone and my HU would present me with some of the setup and TOS screens you get when you first pair the two devices. It definitely presented them to me on the attempt that was successful in getting my microphone/speech recognition to work.
I hope something in there is helpful.
On the topic of media apps, I didn't have the AA compatible version of 'Beyond Pod' or 'TuneIn Radio' installed. I signed up for the beta testing version of Beyond Pod last night and it worked well this morning. My phone gets a little toasty, though.