Increase the size of the buffer to N > 1 songs and allow the device to tell the headphones to skip ahead in the buffer. If "next song prediction" is hard (e.g. the user is clicking around their library), support a device "burst push" mode that lets the device send the first M seconds of a song very quickly.

On a side note, it's interesting that this buffering problem is identical with switching channels on any streaming service, and that the buffering delay is a significant psychological barrier to moving around, and that traditional radio works really friggin' well for what it does.