If I do factory reset, set a different primary account, will I lose all the apps I already downloaded? Assuming I purchased and downloaded a few apps, via the existing primary account from the Android Market: 

If I do factory reset, then set a different primary gmail account, will I lose all the apps I already downloaded?

If not, what is really being erased when a factory reset is done?
Yes, you will "lose" those apps, since they are tied to the Google account rather than to the device. As far as I know, there is no way to transfer a purchased app from one account to another.

A factory reset basically clears the /data partition.