What do the differences between spatial and temporal spectra imply about the structure of turbulence?

Thanks for posing a great question. I would love for Taylor's hypothesis to be uniformly valid! It would mean my dissertation would be finished immediately. Let me take on your cluster of questions one-by-one, albeit out of order.

Will something look non-turbulent in one but turbulent in another?

Strictly speaking, no. There are advantages to spatial measurement, though, particularly when your flow is either bounded (jets, wakes, plumes), or exhibits coherent structures (high-Reynolds numbers). You might be familiar with the framework of model reduction or low-dimensional methods, for which Holmes et al. is the definitive text. Spatial measurement of turbulence that is not entirely stochastic and unbounded (or with periodic BCs) can lead to more optimal eigenfunction descriptions than Fourier modes.

Will structures appear in one that don't appear in the other?

See above: Yes, certainly! A single-point time record makes it hard to elucidate spatial flow structure, especially large-scale ones like that of VLSMs in turbulent boundary layers or the wave packets of turbulent jets. Much of the cutting-edge experimental work in turbulence is toward use of coherent spatio-temporal structures to form practical flow models.

Does combining the information into a spatio-temporal spectrum/structure function/etc yield new insights?

Yes! A major milestone for statistical turbulence models of inhomogeneous flows would be a wavenumber-frequency spectrum. This would fully represent the second-order turbulence statistics, which in most practical cases are what we're after. If you could model up to higher moments in space and time, even better. If you have a spare year or two to read it, I'd recommend Monin and Yaglom on this.

A case with which I'm familiar comes from the field of fluid-structure interaction. A turbulent boundary layer flowing over a deformable surface, say an aircraft hull, will produce displacements in the surface. Which structural modes are excited depends both on the spatial distribution of the forcing and the frequency content of the turbulence. You must have both a spatial and temporal description to even begin modeling this problem. Taylor's hypothesis does not work in this case, as you might imagine.

Will things like intermittency show up in one but not the other?

This is a tricky one. Strictly speaking, if a flow is intermittent, it is not stationary, and I somehow doubt you're interested in such flows (but I could be wrong). But, if one has a flow with spatial coherence, modulation of the turbulence by a very large structure could easily look like intermittency in the time domain, when in fact nothing has changed about the statistics of the flow at all. Spatially-distributed observations (or modeling) would help clarify this.

And if I can measure both, should I invest the time/money/effort? Or should I prefer one over the other?

This very much depends on your problem. Practically, (I sure hope) no one is going to block a publication if you are forced to use Taylor's hypothesis to estimate one-dimensional velocity wavenumber spectra, but you should certainly consider and report at which ranges the assumption is valid (usually large $|\mathbf{k}|$ relative to the integral scale). If you're working with static pressure in shear flow (as I am), then you may want to make the effort— Pressure sources in the velocity field are nonlocal, so Taylor's hypothesis is an even worse assumption.

Experimentally, spatial measurements are often extremely difficult. Farve et al. published a series of papers of space-time correlation measurements that took invention of a new apparatus and many years of experiments to complete. My current work is in atmospheric turbulence, and while some people are lucky enough to fund many tens of anemometer stations, studies with more than a handful of spatial positions are still rare.

I really can't speak to the computational side, except to say that I hope DNS papers with $\omega$-$\mathbf{k}$ spectra will become common soon. It seems to me that it would be easier computationally, but then constraints on grid spacing could pose serious hurdles. A recent paper by Wilczek et al. compares LES wavenumber-frequency spectra to a theoretical model they developed, and I'm keenly interested to see this work develop. The references should be a great resource, too.