8/14: Substantially edited in response to comments: added to 1st part, added new 2nd and 4th parts
If you haven't found the Gentzen-style proof illustrative, I recommend trying the infinitary proof. (Not everyone likes it, but it's at least an alternate perspective on it.) Pohlers "Proof Theory: An Introduction" gives a nice presentation of the proof, and it includes the proof in PA that ordinals below $\epsilon_0$ are well-founded. (This includes that fact that you use $N$-quantifier induction to proof well-foundedness up to $N+1$ exponents, and provides some insight into way additional quantifiers make it have the effect they do.)
One nice feature of the infinitary proof is that the ordinals are outright bounds on the heights of proofs, so if you're comfortable visualizing infinitary proofs, the source of the increase in bounds is quite explicit. (I'm happy to try to explain in detail
It's worth noting that "infinitary" is a bit of a misnomer. The infinitary proof takes the perspective that a proof of $\forall x\phi(x)$ should be a computable function $f$ so that, or answer questionsfor each $n$, $f(n)$ is a proof of $\phi(n)$. Since the functions are all computable, there's nothing genuinely infinitary about it. People usually ignore the "computable" part for expository purposes, since it makes sense without that requirement, at which point it does look infinitary, but possibly you either haven't seen this versionis just because many of the ideas are clearer without constantly rechecking that the operations we're describing really are computable.
$ $
A follow-up point about what ordinals mean in proof theory. As pointed out in the comments, or have and hate$\omega$ doesn't really mean "infinite" it means "an unspecified fixed integer". Similarly, so I won't launch into$\omega+3$ really means "not only is this integer unspecified, but it will take three steps to figure out which integer it is". So in the infinitary proof of cut-elimination, when we say that just yeta proof has height $\omega$, we mean that it is a proof of, say, $\forall x\phi(x)$, where the height of proof of $\phi(n)$ is $g(n)$ with $g(n)\rightarrow\infty$.)
A proof of height $\omega+3$ is a proof with three additional steps below a proof of height $\omega$. More interestingly, a proof of height $\omega+\omega$ might be a proof of $\forall x\phi(x)\vee\forall y\psi(y)$ where for each $n$, we have a proof of $\phi(n)\vee\forall y\psi(y)$ of height $\omega+n$. To find a quantifier-free instantiation of this proof, we'd have to first plug in an $n$ for $x$ and then, at the appropriate level, an $m$ for $y$ to get a proof of $\phi(n)\vee\psi(m)$ of height $g(n)+h(n,m)$.
$ $
Speaking very loosely, the intuitions you describe above are perfectly sensible, but they basically only correspond to what's happening with fairly simple (mostly one quantifier) formulas. Cut-elimination corresponds to extracting computable information, and when you cut formulas with multiple quantifiers together, information has to flow back and forth between the two sides.
This description is literally true when viewed through the lens of the functional interpretation. When viewed in terms of infinitary cut-elimination, these "back and forths" correspond to interleaved cuts: we place many copies of the first proof (more precisely, proofs of $\exists y\phi(n,y)\vee\psi$ for various values of $n$) throughout the second proof. Each of these creates new cuts, which correspond to taking sections of the second proof and placing them inside the many copies of the first proof which we've just created.
$ $
I think your indexing on the relationship between the fast growing hierarchy and proof-theoretic ordinals is off by an exponential. The proof theoretic ordinal of $I\Sigma_1$ is $\omega^\omega$, but it only proves the primitive recursive functions total (i.e. $f_n$ with $n<\omega$ in the fast-growing hierarchy). I'm not finding a reference on the exact relationship, but I would guess that the gap is consistent---that in the way two quantifier induction is like $\omega^{\omega^n}$, the Conway chain notation is like $\omega^{\omega^2}$. So, while two quantifier induction suffices, dealing with Conway chain notation will look like a substantial use of two-quantifier induction (indeed, I think it involves three levels of nested induction, two of which are over two-quantifier formulas, which would line up well with an ordinal of $\omega^{\omega^2}$).
Having said that, your question is still perfectly sensible: how does the back and forth I described above get things that are very fast growing. Suppose the first proof, of $(\forall x\exists y\phi)\vee\psi$, has a sensible rate of growth, say, exponential. The second proof is iterating the rate of growth of the first proof, and can iterate it an ordinal number of times based on the height of the second proof. Since the second proof could easily (given perhaps some additional cuts over smaller formulas) have, say, height $\omega^2$. That is, if we take $f_0(n)=n^n$, $f_{\alpha+1}(n)=f_\alpha(f_\alpha(n))$, and $f_\lambda(n)=f_{\lambda[n]}(n)$, we should hit around level $f_{\omega^2}(n)$ in this hierarchy.
