$\sum|\cos(x_i-x_j)|\ge \sum|\cos(x_i-x_j)|^2 = \frac{1}{2}\sum |e^{i2x_i}+e^{i2x_j}|^2 = \frac{1}{2}\sum 2 + \frac{e^{i2x_i}}{e^{i2x_j}} + \frac{e^{i2x_j}}{e^{i2x_i}}$. Now observe that the later decomposes into sums $\frac{\sum_{i\neq j} e^{ix_i}}{e^{ix_j}}+e^{ix_j}\sum_{i\neq j} \frac{1}{e^{ix_i}}$. Hence we may adjust $x_j$ such that those conjugate numbers are entirely real to minimize the sum. Thus we get for some $v$ ${e^{i2x_i}}^2 = \frac{v}{\overline{v}}$ and thus we may assume they are equal to one of two antipodal values. Back to the original problem, this implies that we can assume some $x_i=90^{\circ}$ and other $x_j = 0^{\circ}$ and by am-gm we get some minimum that is attainable.