The first proof on Wikipedia on Cayley-Hamilton (a direct algebraic proof) goes on about proving the theorem by considering the adjoint to have some comparison for the characteristic polynomial.
Is there any sort of deeper intuition/motivation on the whole proof? How did the first ones find this proof?
Cayley first announced the theorem in 1858, for $2 \times 2$ matrices, and he checked it for many $3 \times 3$ matrices. The general case was shown by Frobenius in 1878. Unfortunately I can't tell what method he used, as the proof is in German. But here is the paper where you can find out about the first full proof that Frobenius gave.
My favorite (and original) proof of the Cayley Hamilton theorem is a direct consequence of the intuition you just gave.
The first question is then, "what are the two isomorphic rings I mentioned in which these are corresponding factorizations?"
Let $V$ be a finite dimensional vector space over a field $k$. One of the rings is $\text{End}_k(V)[t]$. The characteristic polynomial $p(t)$ of $\phi \in \text{End}_k (V)$ naturally lives in $\text{End}_k(V)[t]$. To see this, we view $t \text{Id}_V - \phi $ as having endomorphisms as coefficients, and then take the determinant, which is then in $\text{End}_k (V)[t]$. The other ring is $\text{End}_{k[t]}(V \otimes_k k[t])$. $\Phi := 1 \otimes t - \phi \otimes 1 $ is an element in this ring, and we have a factorization $\text{det}(\Phi) 1_{V \otimes_k k[t]} = \text{adj}(\Phi) \Phi$.
In the isomorphism $$\text{End}_k ( V \otimes_k k[t]) \cong \text{End}_k (V)[t]$$ We have corresponding elements $$\Phi \leftrightarrow t - \phi$$ and $$\text{det}(\Phi) \leftrightarrow p(t)$$ Therefore, the factorization $\text{det}(\Phi) 1_{V \otimes_k k[t]} = \text{adj}(\Phi) \Phi$ corresponds to a factorization $p(t) = f(t)(t-\phi)$ in $\text{End}_k (V) [t]$. And that's the whole idea!
This naturally leads to the question of how we might think about the factorization $\text{det}(\phi) 1_V = \text{adj}(\phi) \circ \phi$ in $\text{End}_k (V)$. There is a nice formality behind this, too. If you're interested in this, there is a great book on the subject called "Linear Algebra via Exterior Products"