Let me sketch a proof of existence of the Jordan canonical form which, I believe, makes it somewhat natural.
Let us say that a linear endomorphism $f:V\to V$ of a nonzero finite dimensional vector space is decomposable if there exist proper subspaces $U_1$, $U_2$ of $V$ such that $V=U_1\oplus U_2$, $f(U_1)\subseteq U_1$ and $f(U_2)\subseteq U_2$, and let us say that $f$ is indecomposable if it is not decomposable. In terms of bases and matrices, it is easy to see that the map $f$ is decomposable iff there exists a basis of $V$ such that the matrix of $f$ with respect to which has a non-trivial diagonal block decomposition (that it, it is block diagonal two blocks)
Now it is not hard to prove the following:
Lemma 1. If $f:V\to V$ is an endomorphism of a nonzero finite dimensional vector space, then there exist $n\geq1$ and nonzero subspaces $U_1$, $\dots$, $U_n$ of $V$ such that $V=\bigoplus_{i=1}^nU_i$, $f(U_i)\subseteq U_i$ for all $i\in\{1,\dots,n\}$ and for each such $i$ the restriction $f|_{U_i}:U_i\to U_i$ is indecomposable.
Indeed, you can more or less imitate the usual argument that shows that every natural number larger than one is a product of prime numbers.
This lemma allows us to reduce the study of linear maps to the study of indecomposable linear maps. So we should start by trying to see how an indecomposable endomorphism looks like.
There is a general fact that comes useful at times:
Lemma. If $h:V\to V$ is an endomorphism of a finite dimensional vector space, then there exists an $m\geq1$ such that $V=\ker h^m\oplus\def\im{\operatorname{im}}\im h^m$.
I'll leave its proof as a pleasant exercise.
So let us fix an indecomposable endomorphism $f:V\to V$ of a nonzero finite dimensional vector space. As $k$ is algebraically closed, there is a nonzero $v\in V$ and a scalar $\lambda\in k$ such that $f(v)=\lambda v$. Consider the map $h=f-\lambda\mathrm{Id}:V\to V$: we can apply the lemma to $h$, and we conclude that $V=\ker h^m\oplus\def\im{\operatorname{im}}\im h^m$ for some $m\geq1$. moreover, it is very easy to check that $f(\ker h^m)\subseteq\ker h^m$ and that $f(\im h^m)\subseteq\im h^m$. Since we are supposing that $f$ is indecomposable, one of $\ker h^m$ or $\im h^m$ must be the whole of $V$. As $v$ is in the kernel of $h$, so it is also in the kernel of $h^m$, so it is not in $\im h^m$, and we see that $\ker h^m=V$.
This means, precisely, that $h^m:V\to V$ is the zero map, and we see that $h$ is nilpotent. Suppose its nilpotency index is $k\geq1$, and let $w\in V$ be a vector such that $h^{k-1}(w)\neq0=h^k(w)$.
Lemma. The set $\mathcal B=\{w,h(w),h^2(w),\dots,h^{k-1}(w)\}$ is a basis of $V$.
This is again a nice exercise.
Now you should be able to check easily that the matrix of $f$ with respect to the basis $\mathcal B$ of $V$ is a Jordan block.
In this way we conclude that every indecomposable endomorphism of a nonzero finite dimensional vector space has, in an appropriate basis, a Jordan block as a matrix.
According to Lemma 1, then, every endomorphism of a nonzero finite dimensional vector space has, in an appropriate basis, a block diagonal matrix with Jordan blocks.
Best Answer
$\DeclareMathOperator{\Ker}{Ker}\DeclareMathOperator{\id}{Id}$The Jordan normal form theorem states:
A slightly hard to piece together (see this question and this question of mine for clarifications) but comprehensive proof of this is given here.
We know that the characteristic polynomial of a linear operator $A$, which I will denote $\chi_A$, is invariant under change of basis. This is seen easily:
Let $q_i:\forall r\in\Bbb{N},\,\Ker(A-\lambda_i\id)^{q_i}=\Ker(A-\lambda_i\id)^{q_i+r}$. Let $B_i=A-\lambda_i\id$. The proof I linked shows that: $$V=\bigoplus_{i=1}^k\Ker(B_i^{q_i})$$ For all the $k$ distinct eigenvalues of $A$. On inspection of the basis vectors of the Jordan basis, one has that there are $\dim\Ker(B_i^{q_i})$ such vectors in the Jordan bases associated with $\lambda_i$ - recall that an eigenvalue can have more than one Jordan block/basis associated with it.
Consider now $\chi_A=\chi_J$ where $J$ is the Jordan Normal Form of $A$. Consider its matrix: it has all the eigenvalues of $A$ on its diagonal, repeated a certain number of times ($\dim\Ker(B_i^{q_i})$ times) and it is triangular. The determinant of a triangular matrix is the product of the diagonal elements, so we easily get that $\chi_A(x)=\chi_J(x)=\prod_{i=1}^k(x-\lambda_i)^{n_i}$ where $n_i=\dim\Ker(B_i^{q_i})$ is the number of times an eigenvalue is repeated on the diagonal in the Jordan form. This means that $n_i=m_i$, where $m_i$ is the algebraic multiplicity of $\lambda_i$.
Therefore the statement in my question is proved.