I managed to solve a very small subproblem:

Let's solve the problem over $\mathbb R$. If you order the elements with all the positive first and the negatives last, you only lose if some final segment of the positives balances some initial segment of the negatives. You can avoid this by building the order inside-out using a greedy algorithm.

You have a pile of negatives and a pile of positives. You have a current sequence. If the total is negative, you add a positive to the left. If the total is positive, you add a negative to the right. As long as the total never becomes zero, you win.

If you have more than one choice for what to add, you can always add in such a way that the total is not zero. You only lose if there is exactly one number left on one of the sides, and that number would perfectly balance the sum. If that number is positive, you're actually fine - because $a_1$ contributes to every sum, it contributes to none of the differences, and so this balanced sum doesn't actually count. Then adding all the negatives, you will never get another balanced sum. If it's negative, just reverse the order and use the same argument.

The problem is solvable over $\mathbb R$, hence over $\mathbb Z$. A failure to solve the problem for a given $k$ can be viewed as a nontrivial solution to a certain set of linear equations. Because there are no solutions over $\mathbb Z$, there are no solutions mod $p$ for $p$ sufficiently large, hence there are no solutions mod $n$ as long as all prime divisors of $n$ are sufficiently large relative to $k$. I believe greater than $k^{k/2}$ is enough.

I independently came up with a proof in the real case that is a bit different from Pace's:

Let's solve the problem over $\mathbb R$. If you order the elements with all the positive first and the negatives last, you only lose if some final segment of the positives balances some initial segment of the negatives. You can avoid this by building the order inside-out using a greedy algorithm.

You have a pile of negatives and a pile of positives. You have a current sequence. If the total is negative, you add a positive to the left. If the total is positive, you add a negative to the right. As long as the total never becomes zero, you win.

If you have more than one choice for what to add, you can always add in such a way that the total is not zero. You only lose if there is exactly one number left on one of the sides, and that number would perfectly balance the sum. If that number is positive, you're actually fine - because $a_1$ contributes to every sum, it contributes to none of the differences, and so this balanced sum doesn't actually count. Then adding all the negatives, you will never get another balanced sum. If it's negative, just reverse the order and use the same argument.

The problem is solvable over $\mathbb R$, hence over $\mathbb Z$. A failure to solve the problem for a given $k$ can be viewed as a nontrivial solution to a certain set of linear equations. Because there are no solutions over $\mathbb Z$, there are no solutions mod $p$ for $p$ sufficiently large, hence there are no solutions mod $n$ as long as all prime divisors of $n$ are sufficiently large relative to $k$. I believe greater than $k^{k/2}$ is enough.