The sum of square roots problem asks, given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ of positive integers, whether the sum $\sum_i \sqrt{a_i}$ less than, equal to, or greater than the sum $\sum_i \sqrt{b_i}$. The complexity status of this problem is open; see this post for further details. This problem arises naturally in computational geometry, especially in problems involving Euclidean shortest paths, and is a significant stumbling block in transferring algorithms for those problems from the real RAM to the standard integer RAM.
Call a problem Π sum-of-square-roots-hard (abbreviated Σ√-hard?) if there is a polynomial-time reduction from the sum of square roots problem to Π. It is not hard to prove that the following problem is sum-of-square-roots-hard:
Shortest paths in 4d Euclidean geometric graphs
Instance: A graph $G=(V,E)$ whose vertices are points in $\mathbb{Z}^4$, with edges weighted by Euclidean distane; two vertices $s$ and $t$
Output: The shortest path from $s$ to $t$ in $G$.
Of course this problem can be solved in polynomial-time on the real RAM using Dijkstra's algorithm, but each comparison in that algorithm requires solving a sum-of-square-roots problem. The reduction uses the fact that any integer can be written as the sum of four perfect squares; the output of the reduction is actually a cycle on $2n+2$ vertices.
What other problems are sum-of-square-roots-hard? I'm particularly interested in problems for which there is a polynomial-time solution on the real RAM. See my previous question for one possibility.
As Robin suggests, boring answers are boring. For any complexity class X that contains sum-of-square-roots (for example, PSPACE or EXPTIME), every X-hard problem is boringly sum-of-square-roots-hard.
