One can sometimes read the rather vague comment that indefinite matrices are "tough to solve" by iterative and direct solvers.
An example would be a saddle point system that arises from the numerical solution of the Stokes equations. For this problem, a discretization can lead to a symmetric linear system and one could apply the conjugated gradient method. In that case, the error can be bounded by \begin{align} \left\| \mathbf{e}_k \right\|_\mathbf{A} &\leq 2 \left( \frac{ \sqrt{\kappa(\mathbf{A})}-1 }{ \sqrt{\kappa(\mathbf{A})}+1 } \right)^k \ \left\| \mathbf{e}_0 \right\|_\mathbf{A} \,, \end{align} where $ \mathbf{e}_k := \mathbf{x}_k - \mathbf{x}_* $ is the error and $\kappa(\mathbf{A})$ is the condition number. For symmetric matrices $\kappa(A) = \frac{\left|\lambda_\text{max}(A)\right|}{\left|\lambda_\text{min}(A)\right|}$.
I understand that $\kappa(\textbf{A})$ increases as e.g. $|\lambda_\text{min}(A)|$ decreases (while $|\lambda_\text{max}(A)|$ remains constant), this makes the system "tougher to solve" in the sense that more iterations are required. But:
How is the indefinite property relevant for iterative solvers (with respect to the example)?
Why is the indefinite property relevant when applying direct solvers?
The conjugate gradient method works only for symmetric positive definite matrices, so there's one reason why indefinite problems are harder to solve by iterative methods. The issue is that conjugate gradient, in a fundamental way, uses the fact that the matrix $A$ defines an inner product $(x,y) \mapsto y^\top A x$. The conjugate gradient method essentially computes a sequence of search directions which are "$A$-orthogonal" to each other. Once definiteness breaks down, you're toast because then a vector can be "orthogonal to itself" and satisfy $x^\top A x = 0$. If you study the CG method, you see that this $A$-orthogonality idea isn't just a minor point of the analysis and is really essential to why the method works. With an indefinite problem, you lose access to this $A$-inner product and you have to do some uglier things to compensate.
Another factor which is a little harder to put into a neat box is the fact that a lot of the most commonly solved symmetric positive definite matrices possess really good preconditioners. The discretized Poisson equation, for example, has incredibly effective multigrid and graph-theoretic preconditioners. Again, with indefiniteness you lose this nice structure and these problems have empirically proven to be much harder to precondition.
As for direct solvers, there's not nearly as big a difference, at least for dense matrices. The nice thing about positive definite matrices is the need to do pivoting for numerical stability is significantly obviated by the positive definiteness. One structural fact that might help illustrate why this is the case is that the largest entry in any row or column of a positive definite matrix is on the diagonal, which is definitely not true in general for indefinite problems. This means you need to do pivoting for symmetric indefinite matrices for stability reasons, which might negatively some structural properties you might want to maintain (e.g. sparsity, low-rank structure, etc.)