If $A^2 + I = 0$ is a matrix equation, all solutions $A \in M(n,\mathbb{C})$ are similar to $$ B = \begin{pmatrix} i I_p & 0 \\ 0 & -i I_m \end{pmatrix} $$ where $i$ is the imaginary unit and $m + p = n$.
Perhaps there is a way to use the Jordan canonical form towards a solution? A hint getting started on this path would be helpful.
On
$A^2+I=0 \implies A^2=-I$. therefore the eigenvalues of $A^2$ are all $-1$, because $A^2$ is a diagonal matrix with $-1$s on the diagonal.
Let $\lambda$ be an eigenvalue of $A$. Note that $\lambda^2$ is an eigenvalue of $A^2$, which is $-1$. Hence $\lambda = \pm i$. Thus $A$ has the same eigenvalues as a matrix of the form $B$ (which is diagonal, so has it's eigenvalues along the diagonal).
Therefore the Jordan canonical form of $A$ will be the same as a matrix of the form $B$ with appropriate $m$ and $n$, and hence $A$ will be similar to a matrix of the form $B$ as they have the same Jordan Canonical form.
Hint: You don't really need Jordan normal form. $A$ has minimum polynomial dividing $x^{2}+1$ (it could possibly be $x+i$ or $x-i$ if only one of $i,-i$ is an eigenvalue), which has no repeated roots. A complex $n \times n$ matrix is diagonalizable ( ie similar to a diagonal matrix) if and only if its minimum polynomial has no repeated roots. The eigenvalues of $A$ are clear, so you are almost home.