I believe Kodak makes a color printer paper that is available in either matt or glossy finish.  It really depends on what the image is and how you want it produced.  When I was working in photography I found that for most portrait work matt finish was better because it gives the texture of a stretched canvas.  Glossy is good for slick prints that have a magazine quality to them.

I'm not sure where you are or what stores are available where you are but you might try shopping at a camera store that handles photographic papers and such as many of them also handle papers for electronic printers.

I hope that helps some.

BTW, your gift idea is an excellent idea.