+1 for Joan's comment.
Matt papers tend to be softer and work better for images that are atmospheric and "softer" in terms of aesthetic. Gloss papers tend to be really plasticky, but the gloss effect works well with high contrast images - typically black & white. Lustre/Satin/Insert other name papers are a good middle ground, but quality varies enormously. For me - print quality is as much about what the paper feels like to touch as it is about the actual print.
If you're on a budget, I'd recommend Marutt's Archival Matt as a great starter (and inexpensive) matt paper, or Fotospeed's Platinum Lustre as an excellent (only just) sub-£1/A4 paper. Any lower than this and I found the quality to be terrible. If you prefer quality over price, then I'd strongly advise getting some tester packs and trying different papers. Ilford, Hahnemuhle, Permajet and Fotospeed all do one, and onlinepaper used to do a Baryta test pack that was a mix of many different ones.