Ok, I’m not sure of things, so take this with a grain of salt. I also bugged pmjdebruijn to help me understand a couple of things clearer, and he was busy so told me to take what he said with a healthy dose of salt as well. So you’re getting multiple doses of salt.
On the good side, any errors will likely bug the smarter folks enough to get them to correct me. 
This is the reason for calibration and profiling of your monitor and the use of soft-proofing print profiles provided by your printer. Calibration and profiling is a bit out of scope for a quick answer, but you should start there.
Assuming you have calibrated and profiled your monitor…
You will want to contact the print shop to obtain a soft-proofing profile from them for their printers. This is usually a function of the type of paper being used as well. For instance, I may want to print something with my print shop, who provides soft proofing printer profiles here: WHCC Soft Proofing Profiles. They provide various profiles for their different paper types (Kodak Professional Supra Endura VC):

You would download the appropriate ICC profile for your intended paper target. This is what you would use to “soft proof” in something like GIMP. I’m not sure which GIMP version you’re using - so I’m going to use 2.8.18 as my example. With your image loaded in GIMP, you’ll now want to see what it will look like using the ICC profile you downloaded previously.
In GIMP, go to Edit → Preferences → Color Management

You’ll want to set your “Print Simulation Profile” to the printer profile you previously downloaded (and set the Softproof rendering intent to “Perceptual” usually). Hit “OK”.
Back on your image, you’ll need to turn on the color proofing display filter to see the proofed result. Open the display filters dialog using View → Display Filters…:

On the left, choose Color Proof and click the right arrow to add it to the active filters. Then click on it in the active filters window to see the options:

Set the Profile to your printer soft-proofing profile (you can leave Intent on Perceptual).
You should now be seeing what your print should look like coming from the printer.
Caveat: someone smarter than me may come along and correct this, but it’s a good rough idea of what the steps would be.
Matte vs Gloss
This is a highly personal choice and will usually depend on the type of print you’re making and what you want the final effect to be. Personally I like the little extra impact a gloss (or sometimes metallic) paper can give to a color print. Colorful images just feel more vibrant on gloss. For B&W images I’ve been happy with matte. This is all personal preference and is an area ripe for experimentation on your part to see what you like. 
Print Resolution
There’s an old rule of thumb that the image viewing distance is usually approximately 1.5 or 2 times the diagonal of the image. With some simple arithmetic + approximations a formula can be worked out where:
PPI ≈ 3438⁄Viewing Distance
PPI ≠ DPI, but I’m making this simplification here anyway.
So what does this all mean? Well, assuming you print A4 (210mm x 297mm), you’d get a diagonal of 14.3 inches (sorry everyone, it’s just the way my brain is wired). So…
1.5 × 14.3 ≈ 21.5 inches.
And,
PPI ≈ 3438⁄21.5 ≈ 160 PPI (at least).
Of course, feel free to go higher than this - at worst you’ll just need to move around a bigger file (but folks can nose up closer to your image and you’ll still retain sharpness).
Quick summary:
Size (view dist.)
5x7 (13in) = 266ppi
8x10 (19in) = 179ppi
11x14 (27in) = 128ppi
16x24 (43in) = 80ppi
Where PPI = image size (in pixels) / intended print size.
So an image that is 4096 pixels wide, printed to 10inches wide = 4096px⁄10 inches = 409.6 PPI
Hope this helps, and welcome to the community! 