Which one was faster when you tried using Eigen? You may also consider Trilinos if you're using C++.
By "generic Laplacian matrix", do you mean a finite difference / finite element discretization of the Laplace operator on some domain, or do you mean the Laplacian of some graph $G$?
Whether or not your solver is overwhelmed as you scale up the number of unknowns depends strongly on the underlying matrix. For example, if $L$ were a band matrix, then direct solution methods like Cholesky require no more space than the original matrix takes up to begin with. On the other hand, if the matrix has a less regular structure -- e.g. it comes from a 5-point stencil in 2D or a random graph -- then matrix factorizations will have a lot of fill-in and CG becomes preferable. In my own experience, the latter case is more common. Generally speaking, for a PDE in 2 dimensions or more, direct methods are faster for problems with less than ~25,000 unknowns, after which iterative methods are the clear winner.
In either case, there's a lot to gain by permuting the matrix so that its bandwidth is reduced. For direct solution methods, this reduces the amount of fill-in; for iterative solution methods, it can enhance locality of reference when accessing the elements of $x$.
Finally, for iterative methods, choosing a good preconditioner is as important, if not more so, than choosing a good solver. Both Trilinos and PETSc have implementations of multigrid preconditioners, for which your problem is the textbook application.