Make recursive chmod faster

I have an installation script that unzips a directory, then recursively chmods its contents.

I'm surprised it takes almost 10 times the time it takes to unzip, to run the following two commands:

find $dir -type f -exec chmod a+r "{}" \;
find $dir -type d -exec chmod a+rx "{}" \;

Am I doing something wrong, is there a faster way to change the chmod of all files and directories?

You can get rid of the find commands by using chmod's X flag:

execute/search only if the file is a directory or already has execute permission for some user (X)

This allows you to set the same permissions on files and directories, with directories additionally being executable, with a single command:

$ chmod -R a+rX $dir

You could do the following (assumming Linux):

cd $dir
chmod -R a+r .
find . -type d -print0 | xargs -0 chmod a+x

This should be much faster than the combination of the two commands you indicated in your question.

Use tar instead. Specifically with the -p, --preserve-permissions, --same-permissions flag.
You won't can't directly zip it, but -z, --gzip, -j, --bzip2 or -J, --xz ought to work well enough. If you really must have zip it's only a | away.