The answers to your questions lie, most likely, in resolution (PPI).
No it doesn't. Increasing the size of a photo makes it neither worse nor better quality. It just makes it larger.
If you had a print of a photo, and looked at it at arm's length, and it looked good, you'd be satisfied. If you then held that same print REALLY close to your nose, it would be much bigger to your eyes. Would you complain that it was suddenly a bad print? Of course not - it's exactly the same print, you're just looking at a much closer view.
No it doesn't. The only possible explanation for this is that you're viewing at greater that 100%. Never do that.
Good. Never use anything else.
Right. And this is the clue. This statement is why I suspect you're messing up the resolution (ppi) when resizing.
So, talk to me about your process. Firstly, what resolution does your lab require for prints?