Find the eigenvector associated with the smallest eigenvalue, not smallest in magnitude

You can always modify the matrix so that the most negative eigenvalue is also the one with the largest absolute value, and hence corresponds to the first in the list returned by EigenVectors.

An upper bound for the largest absolute value of any eigenvalue is the Hilbert-Schmidt norm. So you can rescale your matrix by subtracting this norm times the unit matrix. The eigenvalues will then be guaranteed to be no larger than zero, and therefore the most negative eigenvalue is the one with the largest absolute value.

Here I do this with the random matrix d, nicely constructed by @belisarius to be symmetric:

d = (# + Transpose@#) &@N@RandomInteger[{-10, 10}, {2000, 2000}];

nn = Norm[Flatten[d]]; 
Eigenvalues[d - nn IdentityMatrix[Dimensions[d]], 1] + nn

(* ==> {-762.081} *)

As mentioned, you can then also get the eigenvector this way:

ev = Eigenvectors[d - nn IdentityMatrix[Dimensions[d]], 1];

Update: version 10

In Mathematica version 10, there is another way to get the largest or smallest eigenvalues: using a Method setting with non-default "Criteria":

-Eigenvalues[-d, 1, Method -> {"Arnoldi", "Criteria" -> "RealPart"}]

(* ==> {-762.081} *)

The Arnoldi method is used when only a few eigenvalues of a large matrix are needed. By default it uses the "Magnitude" as the criteria for finding these eigenvalues. But if you specify "RealPart" instead, the eigenvalue with the largest real part is found. Since we wanted the smallest real part, I simply reversed the sign of the matrix and undid that reversal in the end.