Ironically, just an hour or so after I added the bounty, I stumbled on the solution. I wanted info about the song to show on the Android Auto screen, so I found documentation on the mediasession.setMetadata() method. I added code to set the metadata and suddenly the playback controls were there (and the metadata). I think the "Getting your Selection..." message was a clue that it might have been hanging on getting metadata for the song, which was missing before.

This has been a long project with many bumps in the road, but I think I'm in the home stretch now! Just got a new car with Android Auto support, so I can try it out on the road :).