The Greenberg-Hastings model (GHM) is a family of multitype cellular automata that emulate excitable media, exhibiting the nucleation and spiral formation characteristic of such complex systems. In this paper we study the asymptotic frequency of nucleation in GHM dynamics on $\mathbb{Z}^2$ as the number of types, or colors, becomes large. Starting from uniform product measure over $\kappa$ colors, and assuming that the excitation threshold $\theta$ is not too large, the box size $L_\kappa$ needed for formation of a spiral core is shown to grow exponentially: $L_\kappa \approx \exp\{C_\kappa\}$ as $\kappa \rightarrow \infty$. By exploiting connections with percolation theory, we find that $C = 0.23 \pm 0.06$ in the nearest neighbor, $\theta = 1$ case. In contrast, GHM rules obey power law nucleation scaling when started from a suitable nonuniform product measure over the $\kappa$ colors. This effect is driven by critical percolation. Finally, we present some analogous results for a random GHM, an interacting Markovian system closely related to the epidemic with regrowth of Durrett and Neuhauser.