Just had a look at Gallery3 system requirements. At first glance those for PHP look to be met but MySQL has to be 5+ and ccgi is 4.1.11. So problems with that are to be expected.
An upgrade to MySQL is being considered, though timescales are undefined and it isn't imminent.
Possibly Gallery2 would work, though I didn't spot a statement on system requirements for that version. Which version have you installed in the past? Are you trying to upgrade that?
The server 500 errors might well be permissions (chmod) related, the security model has tight requirements on what those can be. The CGI Platform PHP Upgrade FAQ
provides more information.