$C(M)=\{A\in M_n(\mathbb{C}) \mid AM=MA\}$ is a subspace of dimension at least $n$.

Your approach is correct. Let $PMP^{-1}=J$ with invertible $P$ and Jordan form $J$. Then $$ \begin{align} AM=MA &\Longleftrightarrow PAMP^{-1}=PMAP^{-1} \\ &\Longleftrightarrow PAP^{-1} PMP^{-1} = PMP^{-1} PAP^{-1}\\ &\Longleftrightarrow PAP^{-1} J= J PAP^{-1}. \end{align} $$ Thus, we have $$ \phi_P : C(M) \rightarrow C(J) $$ given by $\phi_P(A) = PAP^{-1}$, is an invertible linear transformation with $\phi_P^{-1}(B)= P^{-1}BP$. So, $C(M)$ and $C(J)$ are isomorphic via the isomorphism $\phi_P$. Therefore, $C(M)$ and $C(J)$ have the same dimensions over $\mathbb{C}$.

Then if you prove that $C(J)$ has dimension at least $n$, then the same is true for $C(M)$ too.

Alternatively, as I commented last year, you can also use the general formula given in Centralizer of a Matrix. This gives the following info:

Let $\mathbb{F}$ be a field and $M\in M_n(\mathbb{F})$. Denote by $C(M)=\{A\in M_n(\mathbb{F}) | AM=MA\}$ the centralizer of $M$. The dimension of $C(M)$ over $\mathbb{F}$ is given by $$ \mathrm{dim}_{\mathbb{F}} C(M) = \sum_p (\mathrm{deg}(p))\sum_{i,j} \min (\lambda_{p,i}, \lambda_{p,j}), $$ where $p$ is any irreducible polynomial that divides the characteristic polynomial of $M$, and $\lambda_p= \sum \lambda_{p,i}$ is the exact power of $p$ in the characteristic polynomial of $M$. Here, $\lambda_{p,i}$ are the powers of $p$ in the primary decomposition of the $\mathbb{F}[x]$-module $\mathbb{F}^n$ in which $x$ acts by $M$-multiplication on the left.

By taking $i=j$ only in the double sum, we obtain that $$ \mathrm{dim}_{\mathbb{F}}C(M) \geq \sum_p (\mathrm{deg}(p)) \sum_i \lambda_{p,i} = n. $$

The equality occurs if and only if the minimal polynomial and the characteristic polynomial of $M$ coincide. Moreover, we have in this case, $$ C(M)=\{f(M) | f\in \mathbb{F}[x]\} = \mathrm{span}_{\mathbb{F}} \{ I, A, \ldots , A^{n-1}\}. $$