I'm guessing this is caused by the type of paper used. So what kind of photo paper is best for quality while reducing fingerprints? (inexpensive would be good too, but that comes last)

Glossy paper will always attract fingerprints. Matt paper is finger resistant but doesn't look as good in my opinion.