When I attempt to install the Gallery I receive an Internal Server Error, however, if I go back into the control panel, it shows the Gallery as installed.
Looks like your server is forcibly killing the script after 31 seconds if it doesn't finish running. For an import of an add-on, this can potentially be triggered. I'm not sure why it'd work when uploading the file to be honest as the same code is triggered, but if that works... Otherwise, you may need to contact your host about this limit.
Thanks, I can up the max execution time, however, I have installed the gallery several times on the server and it has never happened before. Any idea why it would be happening now?
There can always be slight variations in execution time. It will vary based on the size of the add-on, software on the server and other things happening. It's possible you were just short of the mod_fcgid limit before so a slight increase is now triggering this error.