Replica exchange molecular dynamics simulations and vibrational spectroscopy calculations are performed using halide-water many-body potential energy functions to provide a bottom-up analysis of the structures, energetics, and hydrogen-bonding arrangements in X-(H2O)(n)(n = 3-6) clusters, with X = F, Cl, Br, and I. Independently of the cluster size, it is found that all four halides prefer surface-type structures in which they occupy one of the vertices in the underlying three-dimensional hydrogen-bond networks. For fluoride-water clusters, this is in contrast to previous reports suggesting that fluoride prefers interior-type arrangements, where the ion is fully hydrated. These differences can be ascribed to the variability in how various molecular models are capable of reproducing the subtle interplay between halide-water and water-water interactions. Our results thus emphasize the importance of a correct representation of individual many-body contributions to the molecular interactions for a quantitative description of halide ion hydration.