Regularity of root spacing of $G(z)=\sum_{n=1}^{\infty} \frac{e^{-n^{2}}}{n^{z}}$
Approximate $G(z)$ by the first two terms, $g(z) := e^{-1} + e^{-4}/2^z$. The zeroes of $g$ are $$- \frac{3}{\log 2} + (2k+1) \frac{\pi}{\log 2} i \approx - 4.328 + (2k+1) 4.532 i \ \mathrm{for} \ k \in \mathbb{Z}.$$ In particular, the zeroes of $g$ are perfectly regularly spaced.
Your zeroes are pretty close to these points, so I suspect that the regularity you are seeing just means that the zeroes of $G$ are pretty close to those of $g$.
Numerically I got these roots with growing imaginary parts :
$-4.3409477472 + i\ 4.4770216332$
$-4.2880579538 + i\ 13.633957460$
$-4.3851693625 + i\ 22.647453867$
$-4.2763847378 + i\ 31.711259005$
$-4.3658043306 + i\ 40.8352457753$
$-4.3147004415 + i\ 49.8019753881$
$-4.3083714889 + i\ 58.9723863592$
...
Regularity and analytic expressions for the exact roots seem both compromised.
EDIT2: Since this is a Dirichlet series (with coefficients $c_n=e^{-n^2}$) and since there is absolute convergence everywhere (by the Weierstrass M-test as noticed by Eric Naslund) we may use the analytic properties of Dirichlet series to conclude that the abscissa of convergence of the Dirichlet series is $-\infty$ so that $G$ is analytic on the whole plane. Applying the Weierstrass factorization theorem we deduce that $G(z)$ may indeed be written as a product involving its roots.
The approximate values were nicely presented by David Speyer so let's compare them to the actual values. I tabulated the distances between the actual and approximative roots to get : $[0.056814, 0.054425, 0.058860, 0.053906, 0.057958, 0.055621, 0.055335]$
Concerning the arguments (from the actual roots) the difference between consecutive arguments $\mod (2 \pi)$ are : $[2.5436, 2.6434, 2.6083, 2.5665, 2.6760, 2.5343]$
Both distance and rotation look regular. This could indicate that the exact roots 'turn regularly around' the approximative roots as $k$ grows. Indeed a 'second order approximation' for the root of index k is :
$$\frac{-3}{\ln(2)} + \frac{(2k+1)\pi}{\ln(2)} i - \alpha e^{i(2k+1)\beta} \approx - 4.328 + (2k+1) 4.532 i - 0.05621 e^{-4.9793i(2k+1)}$$ $$\mathrm{with}\ \alpha=\frac{e^{3\frac{ln(3)}{\ln(2)}-8}}{\ln(2)},\ \beta=-\pi \frac{\ln(3)}{\ln(2)}\ \mathrm{and}\ k \in \mathbb{Z}.$$
To get this I added one term to David's approximation :
$g_3(z) := e^{-1} + e^{-4}/2^z + e^{-9}/3^z$
multiplied by $e$, considered the $e^{1-9}/3^z$ term a 'small perturbation' of $1$ to get : $-e^{e^{-8}/3^z}\approx e^{-3-z\ln(2)}$. Taking the logarithms on both sides and replacing the z at the left with the 'first order' solution returns $z\approx \left(-3+(2k+1)i\pi-e^{-8-\ln(3)(-3+(2k+1)i\pi)/\ln(2)}\right)/\ln(2).$
With this new approximation the median distance is now $\approx 0.0023$ but I'll refrain the search of epicycles in this new astronomy that still requires a Kepler...
EXACT ROOTS - Using the same method (with the exact terms at the left instead of $-e^{e^{-8}/3^z}$) we may find the exact roots by iterations. Let's define : $$f_n(z)=1+e\sum_{m=3}^{n+1} \frac{e^{-m^2}}{m^z}\ \mathrm{and} \ r_1(k)=\frac{-3+(2 k+1) i \pi}{\ln(2)}$$
then the root corresponding to $k$ is obtained by iterations of : $$\ r_n(k)=r_1(k)-\frac{\ln(f_n(r_{n-1}(k))}{\ln(2)}$$
Example for $k=6$ :
$r_1(6)= -4.328085123 + i\ 58.92068184$
$r_2(6)= -4.310848945 + i\ 58.97454441$
$r_3(6)= -4.308195489 + i\ 58.97248418$
$r_4(6)= -4.308369505 + i\ 58.97237420$
$r_5(6)= -4.308372230 + i\ 58.97238650$
$r_6(6)= -4.308371466 + i\ 58.97238640$
$r_7(6)= -4.308371487 + i\ 58.97238636$
$r_8(6)= -4.308371489 + i\ 58.97238636$
(the distance from the actual value is more than $16$ times smaller at each iteration, the same is true for $k=0$).
Nice problem!
OTHER LAYERS - Let's investigate the 'second layer' detected by deoxygerbe with first roots at :
$-12.3840905498065732 + i\ 7.69101465838042938$
$-12.2523952898036964 + i\ 23.2196214862555024$
$-12.3153823799387642 + i\ 38.8071497678513693$
The 'first layer' was generated by the solutions of $0=e^{-1^2}/1^z+e^{-2^2}/2^z$ (first+second term of the series).
The 'second layer' seems to have been generated by the solutions of $0=e^{-2^2}/2^z+e^{-3^2}/3^z$ (second+third term of the series). Solutions may be obtained from the previous ones with the replacement of $-3=1^2-2^2$ by $-5=2^2-3^2$ and of $\ln(2)=\ln(2/1)$ by $\ln(3/2)$ to get : $$r^{(2)}(k)=\frac{-5+(2k+1)i\pi}{\ln(\frac32)}$$
I used the notation $r^{(2)}_k$ with the thought (comforted by your clear picture!) that other layers should exist near : $$r^{(L)}(k)=\frac{-(2L+1)+(2k+1)i\pi}{\ln(\frac{L+1}{L})}$$
Indeed a solution near $r^{(3)}(0)$ (the 'third layer' at $x\approx -24.33$) is : $-24.400057077391736+ i\ 10.878966908988947$.
Further the abscissa of the 'fourth layer' near $-40.33$ with ordinates near $14.0$ and $42.2$ seem to correspond rather well to your picture!
Anyway let's try to handle all the layers at once and define : $$f^{(L)}_n(z)=e^{L^2}L^z\left(\sum_{m=1}^{n+1} \frac{e^{-m^2}} {m^z}- \frac{e^{-(L+1)^2}}{(L+1)^z}\right)$$ $$r^{(L)}_1(k)=\frac{-(2 L+1)+(2 k+1) i \pi}{\ln(\frac{L+1}{L})}$$
then the root corresponding to $k$ on the layer $L$ should be obtained by iterations of : $$\ r^{(L)}_n(k)=r^{(L)}_1(k)-\frac{\ln(f^{(L)}_n(r^{(L)}_{n-1}(k))}{\ln(\frac{L+1}{L})}$$
This seems to provide all the 'visible' roots but I won't exclude the existence of other families (involving for example the first and third term) after all I missed an infinity of layers... :-)