Actually, yes, another photo with some slightly different greenery would be a terrific solution if possible. But it would have to be pretty dark greenery, yes? Or possible to be made pretty dark, at least.
That's not too bad. You might get a passable 8x8 inch canvas out of it. Do you think she would be happy with that? (Assuming we can remove the guy, of course).
Yes, that seems the most likely cause. If you have other prints from the same lab that do match your screen, and if you're still safely in sRGB, there's no reason why this batch shouldn't have matched too.
Even by the standards of eleven years ago, 1.5 megapixels was oddly small. Are you sure you have the exact file that came out of the camera? Not a copy that's been shrunk by an email program, perhaps?
If they really do stretch it, then it means you have to leave them some area to stretch. Eg give them an inch to stretch into two inches. But if you don't know exactly how much to allow, then all your questions about sizing and sharpening are completely moot.
DON'T trust them with this important task. Do it yourself.
Great! So what's the problem?? Just close your logo PSD file, and never open it again.
When you need to use it on a photo, go to File>Place, exactly as my instructions say.