This gets stranger, I plan on moving the PHP binary to another location and trying it there.
No FTP involved, did a wget and untarred on the server.
Since I am running as an Apache module, I modified the .htaccess to use the CGI version of php instead. Knowing all the modules I need are not in DH's PHP, I finished setup, and things were at least working, but not the features I wanted.
I then copied my custom PHP that I use for Horde to a cgi-bin directory inside the gallery directory, and modified .htaccess to point to the custom PHP, this caused the Internal Server Error, Premature end of script headers. Curious, this worked with the stock PHP CGI, so I assumed it was something compiled into the binary that gallery didn't like.
Re-compiled PHP to cut out some un-needed stuff threw this into the gallery directory, and still a server error. Thinking something wierd was up, I again pointed to the Horde PHP binary, but this time, I left it in the Horde directory and pointed there. Things worked fine.
I thought I lost my mind, so I copied the stripped down PHP to horde, and it still worked fine. I copied both binaries back to the gallery directory, changed .htaccess again, and again, a server error.
It turns out, I had changed the cgi-bin directory to group write, and the server does not like that. I just found a link to the discussion on this, so for any others out there,
DIRECTORY CONTAINING PHP BINARY CANNOT BE GROUP or WORLD WRITABLE
Thanks for listening, thanks for the help, and maybe I will point this out to DH support.