Is it possible to give a nice characterization of matrices $A \in R^{n \times n}$ which are self-adjoint with respect to *some* inner product?


These matrices include all symmetric matrices (of course) and some nonsymmetric ones: for example, the transition matrix of any (irreducible) reversible Markov chain will have this property. 


Naturally, all such matrices must have real eigenvalues, though I do not expect that this is a sufficient condition (is it?).


About the only observation I have is that since any inner product
can be represented as $\langle x,y \rangle = x^T M y$ for some positive definite matrix $M$, we are looking for matrices $A$ which satisfy $A^T M = M A$ or $M^{-1} A^T M = A$. In other words, we are looking for real matrices similar to their transpose with a positive definite similarity matrix. 



matrices self-adjoint with respect to some inner product
In addition to having real eigenvalues, the matrix will have to be diagonalizable, i.e., there have to be enough eigenvectors to span $R^n$. Once these conditions are satisfied, you can take a basis consisting of $n$ eigenvectors and define an inner product by declaring these basis vectors to be orthonormal. That inner product will make your matrix self-adjoint, because there's an orthonormal basis with respect to which the matrix is diagonal with real entries on the diagonal. 


