Why does my iPhone select a random song when I connect my headphones?
This bug was introduced in iOS 10, and the same thing happens when you ask Siri to “play music,” or even if you pull up the Control Center’s playback controls.

If you Pause, then Resume only a short while later, the app remembers where you were. But leave it be for an hour or two, and it will forget. At that point it will try to shuffle your entire library when you start music playback.

If you open the Music app, it will suddenly remember which song or playlist you were playing last, and you can Play from there.

Until Apple fixes it, I’m afraid that’s the only workaround.

Edit: I haven’t encountered this issue since iOS 10.1.1.