Is there a natural way to find describe all the equivalence classes of $F^{n\times n}$ under equivalence, F an arbitrary field? Here equivalence is just the normal definition: $A$ is equivalent to $B$ if $\exists$ invertible $P,Q$ s.t. $A=PBQ^{-1}$.
Also is there a related way to describe equivalence classes under matrix similarity? ($A$ is similar to $B$ if $\exists$ invertible $P$ s.t. $A=PBP^{-1}$.)
Equivalence is a rather big relation, generated by arbitrary row and column operations. Thinking of the matrix representing a linear transformation, this amounts to the freedom to independently change basis in the domain and codomain of the map. It turns out that two matrices are equivalent if and only if they have the same rank.
Similarity is a smaller relation, generated by simultaneous row and corresponding column operations that are tied together. Thinking of a linear transformation, this amounts to the freedom to change the basis, but in both the domain and codomain simultaneously. It turns out that two matrices are equivalent if and only if they have the same normal (a.k.a. canonical form), but this form depends on the field. At one extreme, if $F = \Bbb{C}$, which is algebraically closed, you get Jordan normal form. If you cannot necessarily guarantee that all the eigenvalues of the matrix lie in the field $F$ (say when $F = \Bbb{Q}$), you can use rational normal form.