The first step is to make sure that your monitor is color calibrated. Some ways to validate that you have done that correctly exist in this previous answer: How can I Validate that my monitor is color calibrated?
Once you have that set, you need to look at the color space that you are embedding in your images, and make sure that that matches what the accepted color space is on the printer that you are choosing.
I would recommend downloading the EZPrints(since you are using them as a Power user) ICC profile that can be found here. Use that to soft proof your images in Photoshop and make sure that everything looks as you would expect. The link that Andy provides also goes into some detail about the levels and what to look for in that which may be helpful to you.
Once you have a properly calibrated workflow, and you take the time to soft proof, you should rarely or ever be surprised by the output that is delivered to you. Good luck!