Agradeço a todos pelas sugestões, finalmente encontrei uma solução muito boa e queria compartilhá-la aqui para futuros leitores!
Por fim, consegui ajustar nossa arquitetura de banco de dados, combinando / removendo algumas tabelas, o que simplificou o design geral e reduziu o tempo necessário para executar o script de criação. Eu também reescrevi nosso script de criação para que ele executasse uma consulta por tabela em vez de três consultas (uma para criar a tabela, segunda para alterar a tabela para adicionar os índices, terceira para criar as chaves estrangeiras). Essas duas coisas deram uma grande melhoria na execução do script, ele passou de cerca de 50 segundos em média para 8 segundos!
Outra coisa que fizemos e que faz uma grande diferença para a experiência do usuário foi criar um serviço que seja executado independentemente em um de nossos servidores, que não fará nada além de criar novos bancos de dados que ficarão vazios aguardando uma nova inscrição de usuário. Quando um usuário inscrever sua conta é simplesmente atribuído ao próximo banco de dados vazio disponível. Nós o configuramos para que o serviço de criador do banco de dados não chegue mais que 100 à frente das necessidades reais da nossa conta. Esse design diminuiu o tempo que o usuário espera ao assinar por 1 ou 2 segundos. Tudo parece um pouco "hacky", mas no final é uma grande melhoria!