Here a direct approach. Recall the power-series \begin{equation*} \arccos(z) = \frac\pi2 - \sum_{k\ge0}\binom{2k}{k}\frac{z^{2k+1}}{4^k(2k+1)}. \end{equation*} From this series it is clear that $\arccos(x^Ty)$ is conditionally negative definite (because it is of the form "const $-$ positive definite").

Here a direct approach. Recall the power-series \begin{equation*} \arccos(z) = \frac\pi2 - \sum_{k\ge0}\binom{2k}{k}\frac{z^{2k+1}}{4^k(2k+1)}. \end{equation*} From this series it is clear that $\arccos(x^Ty)$ is conditionally negative definite (because it is of the form "const $-$ positive definite").

EDIT: (15/12/2015). Here are some more details. Observe that with the above powerseries representation, we have \begin{equation*} f(x_i^Tx_j) = \frac\pi2 - k(x_i,x_j), \end{equation*} where $k(x,y)$ is a positive definite kernel (to see this observe that the power series has nonnegative coefficients, and since $(x_i^Tx_j)^{2k+1}$ is pointwise product of kernels, it is itself a kernel).

Thus, we have in particular that the matrix $F := [f(x_i^Tx_j)] = c11^T-[k(x_i,x_j)]$, so that it immediately follows \begin{equation*} z^TFz = c(z^T1)^2 - z^TKz \le 0, \end{equation*} because the first term is zero whenever $z^T1=0$ (as stipulated for cnd matrices), and because $z^TKz \ge 0$ as $K$ is a kernel.

Note: The above argument does not yield that $f^n$ is cnd (it may likely not be cnd, but I don't have time right now to think about it).