Where to begin...

Ok I think the "Pro" in the printer's name is a reach... Based on their website and definitely on their email response to you, I don't see evidence of any colour management process at all. It reads to me like a mass-market e-print products service, not a professional print-maker.
You mention you "calibrated" your monitor, and by that I assume you mean you profiled it too. That's good. But you don't mention the print process. There's no mention on their site of the specific equipment, media, etc. Without an accurate profile for that you're throwing darts blindfolded.
And with the feel I'm getting about that print provider, I suspect you're unlikely to get anything useful from them in that regard. (I spent ages with similar providers on the same topic and not only were they applying image adjustments/corrections on their machines despite instructions, their output didn't even remotely match their provided icc profiles, there was a ton of variance, and they blamed their profiling service provider for it lol.

)
Anyhow you can try to get a colour profile from them so that you've got something (somewhat) usable for soft-proofing. But anticipate a lot of trial-and-error before you get something you're happy with..., at least until you try a very different print (colour range, tones, whatever) and have to repeat similar for that one... Or it's printed by a different employee. Or on a different machine. Or at a different time of day. Or they changed the media load. Or...
Ultimately my recommendation is either find a professional print-maker to work with, ideally local to you to make the back-and-forth much easier, or bite the bullet and get your own printer (assuming this isn't commercial volume) and buckle down for a lot of learnin' lol. Because altho these kinds of print product providers may seem convenient or economical, if you care about the image quality / consistency I doubt they'll ever measure up. Since you mention you're new to colour management, the first option might be better (at least to start), and they might share some knowledge with you too.
Otherwise, use their profile if they have one (it's probably a bad one), make your file, send it, and then forget about comparing print to soft-proof after, just accept what they give you like it's from your local photocopy shop. And expect it to be different each time even on the same file. And if that's not satisfactory, then see previous recommendations. (Technicallyyyy you could get your own custom profiles made for test prints they give you and proof with those, but since you have zero control over the print process / variation, I feel it's a waste of time.)
Hope that helps.
Edit: for your specific questions, if you adjusted your monitor's brightness and white balance, and then subsequently edited your images differently to suit your eyes' taste and sent that to them, yes you should get a different print. But as above good luck getting any consistent results from it. (You could get different results even if you made zero changes and re-sent the same file!

)