A) Your replacement iPhone will have whatever iOS was installed when it was originally placed in the queue for device replacements. That probably happened quite some time ago, perhaps even prior to iOS 7 being released.
Consider this; if you went to a retail store today and bought a brand-new iPhone 5 in the box (assuming that such a retail store still had leftover stock to sell), would it have the iOS that was available when it was first put in the box and shipped to the store? Or would the store open up boxes periodically, update the iOS, and then reseal the box?
The iPhone 5 was discontinued before iOS 7 was released. Therefore, it is unlikely that a replacement iPhone 5 would have an iOS installed that was not yet officially released at the time of device manufacture.
B) That's perfectly normal behavior. You cannot restore a backup that uses a newer iOS than the device itself is currently running.
C) Yes, because it's two separate processes. One: Update the iOS. Two: Restore the backup.
Did the tech make sure you'd created a backup of your original device?