If one's intent is to understand the comments in Fearless Symmetry, then an investigation of the actual subject at hand (Galois theory and, more particularly, algebraic number theory) will be more revealing than an enquiry into generalities about the concepts of structure and richness.

In this direction:

Regarding Example 1/Question 2: Literally, the structure on the set of solutions is that it is a set equipped with an action of the Galois group (as was already noted by several people).  

Regarding Example 2/Question 1:  There has [already been](http://mathoverflow.net/questions/2791)  an MO question about what number theorists mean when they speak of understanding the group $G_{\mathbb Q}$, which is relevant to this question too.  In any event, in the quoted example, as in many similar statements in the literature, "structure of $G_{\mathbb Q}$" is a short-hand for a number of problems related to the study of $G_{\mathbb Q}$, first and foremost being the study of the representations of $G_{\mathbb Q}$ and their relationships to (i) automorphic forms and (ii) motives.

Note that $G_{\mathbb Q}$ itself has to be thought of not just as a group, but as a group
equipped with conjugacy classes of embeddings $G_K \hookrightarrow G_{\mathbb Q}$ for
each completion $K$ of $\mathbb Q$ (so $K$ is $\mathbb R$ or $\mathbb Q_p$ for some prime $p$), whose images topologically generated $G_{\mathbb Q}$ (by Cebotarev density) in an
extremely overdetermined way.  

The theory of representations of $G_{\mathbb Q_p}$ itself has a deep theory, involving $p$-adic Hodge theory among other tools, and this should be thought of as being included in the "rich structure" being alluded to.

In summary: I think that such assertions are typically short-hand allusions to a deep and important (in the eyes  of those making the assertion, at least) set of problems, techniques, and theorems related to the object at hand; that is the certainly the case in this instance.  At least in the case of Example 2, they do not admit a superficial description in terms of some formal notion of "rich structure".