When you factory reset you loose all inputted data, account log-ins and such, and post installed apps, but your contacts should sync once you enter your account info and the device has a chance to update. I've seen it take up to 24 hours for contacts to fully sync. You should have only lost your gallery items if you chose to wipe memory with the reset, however I've seen it happen without that option, but ideally it is not supposed to touch them unless you opt to. Ideally.
Meanwhile, if your memory is still showing full after a reset, you can do several things but the two I would try are; going to your memory/storage settings and checking what is showing for each category, i.e. Apps, Music, Downloads etc. this will tell you where your memory is being used. If your memory is being eaten up by downloads, music, and pics then you can act on that information make adjustments by transferring items off of the device. These items shouldn't have been affected by the reset, unless you chose to wipe memory with the reset. If these totals are low but your device is still showing a lack of memory the second thing I would do is another factory reset. There may have been some residual items that weren't wiped or shown as wiped with the first reset, and since you've already done one reset doing it again in a short time shouldn't cause you anymore pain than the first time. This should ensure that all of the data from your messaging app, email, Facebook, and all of that are cleared.