Glossy or matte...the paper surface is usually irrelevant. What do you mean by "bad"? Blurriness? Color cast? If it's a color cast that's the problem, then you need to make sure your monitor is calibrated to the standards of your printer.
Also, you have to consider your resolution. Many (usually consumer) digital cameras shoot images at 72 dpi resolution which is intended for use on the WEB. When PRINTING an image, standard is 300 dpi for good quality images. I think people are really mislead by companies when it comes to "MEGAPIXELS". Some 5.0 MP digital cameras will say "Take pictures as large as 20"x30"!!" But technically...you can print that image the size of a football field if you wanted to...
When you convert a 5.0 MP image into 300dpi resolution you can only print a standard "good quality" image around 8x10 inches. Any larger and you get interpolation which are added pixels which are "made-up" to fill in the gaps and degrade the image the larger you resize it.
But if you want to know...the paper which many consumer labs and the vast majority of expensive pro-labs print colored images on (w/Lightjet, Chromira and other "continuous tone" high-resolution processes) is Fuji Crystal Archive. It's pretty much a standard.