On system restore, will I lose my software updates? I have a Samsung Galaxy S3 and have it updated to 4.1.2 from ICS.
If I restore my phone to factory settings (either by going to settings or by rooting), will I lose my updates?
If so, is there any other way to restore without having the above setbacks?
Yes, you'll lose your updates, along with any other installed app that didn't come with stock. But you will be able to re-update the apps via Google Play, and you won't lose any purchases you made (they are stored forever on the Google cloud).

I'm not sure why you're concerned about it, though. I can understand not wanting to lose your settings and data, but the only downside to losing app updates is the time and bandwidth required to re-update them afterwards.

Edit: You are probably asking about OS updates. Your phone does not keep an original OS image. Thus, once you update your OS (either by OTA updates or by installing a custom Rom), you will not be able to revert to the older Android version. Doing a factory reset should just reset the phone to a clean slate of the current Android version.