Given my comment about trying with public read permissions etc. above, I have re-tested permissions locally.
chmod -R 550 cgi
seems to be the minimum required permissions to read and execute. I'm running sql-ledger (a cgi program which writes within the directory), so locally the minimum required is:
chmod -R 770 cgi
I had left the permissions really loose from when I was trying to get nscgi to execute scripts instead of displaying them!
Public read/write is not necessary. Thanks Dave for suggesting (via irc) that I test them again.