Checked with the host, and the "solution" was rather simple.
If anyone is getting the same 500 Internal Server Error after following the installation guide correctly, then try this, it worked for me:
Set map permissions to 755
Set all files permissions (inside the map) to 644
Go to yoursite.com/install.php
Worked like a charm for me