See the paper "On Sampling-based Approximate Spectral Decomposition" by Sanjiv Kumar, Mehryar Mohri & Ameet Talwalkar (ICML 2009.). It uses sampling of columns of your matrix.
Since your matrix is symmetric you should do the following:
Let A be your n*n matrix. You want to reduce the computation of the eigenvalues of an n*n matrix to the computation of the eigenvalues of an k*k matrix. First choose your value of k. Let's say you choose k=500, since you can easily compute the eigenvalues of a 500*500 matrix. Then, randomly choose k columns of the matrix A. Contruct the matrix B that keeps only these columns, and the corresponding rows.
B = A(x,x) for a random set of k indexes x
B is now a k*k matrix. Compute the eigenvalues of B, and multiply them by (n/k). You now have k values which are approximately distributed like the n eigenvalues of A. Note that you get only k values, not n, but their distribution will be correct (up to the fact that they are an approximation).