I just noticed the same problem on my 4S tonight. I took pictures of the kids on the porch carving their pumpkins and I thought maybe it was just the flash causing the issue, but after seeing your pictures I am second guessing myself.
OP: If I am understanding you correctly the Apple store offered to replace it for you, but it would be a service replacement correct? I'd think it'd still be a new 4s just minus the packaging. Could be wrong though, I'll post back after going to genius bar tomorrow.
They indeed give you a new one but I didn't want a service replacement. Maybe it's just me but if my phone is defective out of the box, I want a full replacement, not a phone made specifically to be a replacement. (if that makes any sense)
----------
Are your pictures in completely dark rooms hit or miss in terms of clarity? I feel like every 2nd, 3rd, or 4th photo is clear and the rest are blurry.
I've tested my camera out multiple times and it's constantly blurry. I took it to Apple and they confirmed the issue when they took it into the back to test it out. No go.
----------
This makes no sense to me. If the replacement phone is new and you get a chance to inspect it first, this is the best of both worlds. Now you run the risk of getting a new phone in box with another problem. You could already have a new perfectly working phone in your hands. And if it did not meet your expectations then you could have turned it down??
I've personally had bad experiences with this service replacement phones. Whenever I got a service replacement, a new issue will appear weeks or months later. When I had my 3GS, I kept coming back for a new one where they eventually gave me one from a brand new retail box. Issue free since then.