Haven't had an issue on either device (I own both) with the Play Store for me. As waydavis said, it's actually a ton quicker on the One for me than it was on my Epic. Perhaps it's something with the way your network is prioritizing traffic? At a minimum, since you're experiencing it on multiple devices it sounds less like a One issue and more like a Play Store or networking issue.