Why is the Galois Correspondence intuitively plausible?

I'll limit the discussion here to finite extensions of fields. There is a Galois theory for algebraic extensions of possibly infinite degree, and this is an essential tool in modern number theory through the role of Galois representations. You could say "proof of Fermat's Last Theorem" is a widely known result that would be impossible without Galois theory (and a whole lot more mathematics).

To appreciate what makes the Galois correspondence intuitive, keep in mind the following points.

1. The mappings in both directions for the Galois correspondence make sense for an arbitrary finite extension of fields $K/F$, but only for Galois extensions are these two mappings actually inverses of each other. For example, $\mathbf Q(\sqrt[n]{2})/\mathbf Q$ has a trivial automorphism group when $n$ is odd, but there are lots of intermediate field extensions if $n$ has lots of factors (see my reply to the MSE question here). It's worth thinking about why the Galois correspondence doesn't work for $\mathbf Q(\sqrt[3]{2})/\mathbf Q$ or $\mathbf Q(\sqrt[4]{2})/\mathbf Q$ but does work for $\mathbf Q(\sqrt[3]{2},e^{2\pi i/3})/\mathbf Q$ and $\mathbf Q(\sqrt[4]{2},i)/\mathbf Q$. There is something that happens when we adjoin all the roots of $x^3-2$ to $\mathbf Q$ or all the roots of $x^4-2$ to $\mathbf Q$ that doesn't work when we adjoin only a proper subset of the roots to $\mathbf Q$. Can you articulate what that is?

2. To give an answer to the question at the end of the previous item, expressed in the simplest way, we need to give some intuition behind the magic of splitting fields compared to finite extensions that are not splitting fields. I think the most basic explanation of why splitting fields (normal extensions) are so special is the symmetric function theorem: every symmetric polynomial in $r_1, \ldots, r_n$ is a polynomial in the elementary symmetric polynomials of $r_1, \ldots, r_n$. Because the elementary symmetric polynomials in $r_1, \ldots, r_n$ are the coefficients of $(x-r_1)\cdots(x-r_n)$, if that polynomial has coefficients in $\mathbf Q$ then all symmetric polynomial expressions in $r_1, \ldots, r_n$ are going to be rational, and here is why that's such a big deal: it shows that every number in $\mathbf Q(r_1,\ldots,r_n)$ has all the other roots of its minimal polynomial over $\mathbf Q$ already in that field. If $K$ is a splitting field over $F$ of some polynomial $f(x)$ then every $\alpha \in K$ has all the other roots of its minimal polynomial over $F$ also in $K$. That is the "deep underlying truth" about Galois extensions, which can be proved using the symmetric function theorem before you prove the Galois correspondence works. Modern accounts of Galois theory do not depend on this approach, but earlier accounts of Galois theory did rely on it.

3. Galois extensions exist in great abundance: a finite extension of fields $K/F$ in characteristic $0$ (land of intuition) can always be enlarged to a finite Galois extension $K'/F$, so we can take advantage of Galois extensions to solve problems not originally expressed in the setting of Galois extensions.

4. The issue of Galois extensions requiring separability should be considered a technicality not directly relevant to your intuition: intuition takes place in characteristic $0$, where all irreducible polynomials are automatically separable. Intuitively, Galois extensions = normal extensions. This is not generally true in characteristic $p$, but you get intuition for Galois theory in characteristic $0$, where it is true and the symmetric function theorem explains why the symmetry in the Galois correspondence works for Galois extensions.

The Galois correspondence is profound in number theory because it leads to a highly nonobvious way of turning prime ideals into field automorphisms (this uses Galois theory for number fields and finite fields). The technical term here is "Frobenius automorphism associated to a prime ideal".

Another reason the Galois correspondence is profound is that it is a template for similar correspondences elsewhere in mathematics. There are inclusion-reversing correspondences between

a) subgroups of ${\rm Gal}(K/F)$ and intermediate fields between $K$ and $F$,

b) subspaces of a finite-dimensional vector space and subspaces of its dual space,

c) subgroups of a finite abelian group $A$ and subgroups of its dual group ${\rm Hom}(A,\mathbf C^\times)$ (generalizing to all locally compact abelian groups by Pontryagin duality)

d) subvarieties of affine $n$-space over $\mathbf C$ and radical ideals in $\mathbf C[x_1,\ldots,x_n]$,

e) subgroups of the fundamental group of a nice space $X$ and covering spaces of $X$.

All of these correspondences have similar features and it happens that historically the correspondence with field extensions (Galois correspondence) was found first.

Considering example (c), if you define characters of an arbitrary finite group $G$ in the same way as you define characters of a finite abelian group (homomorphisms from the group to $\mathbf C^\times$), you're going to lose a lot of the nice properties because homomorphisms $G \to \mathbf C^\times$ can only see $G$ as far as the quotient group $G/[G,G]$ (abelianization of $G$). To make character theory work well for arbitrary finite groups, we have to allow irreducible representations of dimension greater than $1$.

Well, the thing to say is that Galois correspondence is an excellent first example of an important general concept of category theory, namely adjoint functors.

But of course that would have been meaningless in Galois's time! Maybe the thing which makes it profound is that it was a profoundly original thing coming from such a young person.

Anyone can appreciate its crisp and somewhat unexpected conclusion: the structure of the field extensions is reflected in the structure of subgroups. Then after appreciating this, one has a fine example of adjoint functors.

Insight about the roots of a polynomial over a field was gained by translating the problem to the category of groups, where the problem was different. Looking for subgroups of a group (one operation) seems easier somehow than looking for intermediate fields in a field extension (two operations.)

I'll try to line it up with the questions you asked:

1. what deep "underlying truth" about the algebraic structure of fields does this theorem reveal?

Well i'd turn that on its side: it's not revealing a thing about the algebraic structure of fields, it's revealing a strong connection between the category of field extensions and the category of groups. The thing that makes it so interesting is that the connection is strong and informative.

2. Why should we expect that by studying the symmetries of a field extension, we can recover the structure of whole field itself

A priori I'm not sure one should expect such a nice connection. The fact that it exists and works is the whole reason it is impressive. Nevertheless, Galois's observation isn't completely out of the blue: it's not hard to show that symmetries of roots lead to field extension automorphisms, and then the questions about whether or not you can do every permutation with an automorphism and consequent questions lead to a pretty natural investigation.

One gains a retrospective appreciation for the way things work by studying the basic results that make the correspondence work. And also, pay special attention the concepts that arose along the way: separability of extensions, normality of extensions.