Make sure the headphones plug is completely inserted into the headphones jack of the shuffle. The fit with new EarPods may be tighter than expected, especially if the shuffle is also fairly new. See pictures in this document
http://support.apple.com/kb/ts3572
Not having the headphones plug completely inserted may have an effect on sound quality, although you can still hear some sound (in mono not stereo). That may be the "flatness" you describe.
Press and hold on the center button is the command to use VoiceOver to change the current playlist. Not sure why that would have the effect of improving the sound quality. If you have not set up VoiceOver on the shuffle, you may want to try doing that to see if it makes any difference.
http://support.apple.com/kb/ht4322
Sounds like you tried doing a Restore already, so it's not a problem with software on the shuffle. Since it works fine with the included headphones, the headphones jack on the shuffle is probably OK.
It's possible that the headphones that come with the iPhone 5s are not exactly like the EarPods sold separately.
