When I first got into this years back I would print at Staples. I had to play around a bit to get it right.
First, they would convert any JPEG files to PDF so they could print. I had to tell them DO NOT FIT TO PRINT. It's an option when you go to print which resizes the image. When they would print from PDF without fit to print, they were almost always right.
Second, keep in mind some covers on this site are not sized correctly, so if one or two specific images are giving you trouble, download GIMP or some other free photo editor and check to make sure they are the right image size (there are tutorials in the forums)
Third, printing covers (especially retail covers) isn't exactly fair use. In fact, a good lawyer could probably argue it is blatant infringement. Some workers may say no. If they do, I wouldn't recommend to fight it, you likely won't win. Just try and go when someone else is working.