We analyze the mean rest-frame ultraviolet (UV) spectrum of Type Ia Supernovae (SNe Ia) and its dispersion using high signal-to-noise Keck-I/LRIS-B spectroscopy for a sample of 36 events at intermediate redshift (z=0.5) discovered by the Canada-France-Hawaii Telescope Supernova Legacy Survey (SNLS). We introduce a new method for removing host galaxy contamination in our spectra, exploiting the comprehensive photometric coverage of the SNLS SNe and their host galaxies, thereby providing the first quantitative view of the UV spectral properties of a large sample of distant SNe Ia. Although the mean SN Ia spectrum has not evolved significantly over the past 40% of cosmic history, precise evolutionary constraints are limited by the absence of a comparable sample of high quality local spectra. Within the high-redshift sample, we discover significant UV spectral variations and exclude dust extinction as the primary cause by examining trends with the optical SN color. Although progenitor metallicity may drive some of these trends, the variations we see are much larger than predicted in recent models and do not follow expected patterns. An interesting new result is a variation seen in the wavelength of selected UV features with phase. We also demonstrate systematic differences in the SN Ia spectral features with SN light curve width in both the UV and the optical. We show that these intrinsic variations could represent a statistical limitation in the future use of high-redshift SNe Ia for precision cosmology. We conclude that further detailed studies are needed, both locally and at moderate redshift where the rest-frame UV can be studied precisely, in order that future missions can confidently be planned to fully exploit SNe Ia as cosmological probes [ABRIDGED].