Here's how to keep that from happening.
The culprit — as you might have suspected if you caught it on your head unit's display — is Pandora's auto-play feature that's meant for Bluetooth-enabled devices. I think what's happening is the phone first sees the Bluetooth in the head unit (I've got the Pioneer 4100) and so Pandora fires up. By the time Android Auto kicks in, Pandora is grooving away.
To keep that from happening, just go into the settings menu, hit "Advanced," and then uncheck "Enable automatic launch" under "Bluetooth for devices."
That should take care of it.