We construct models for strongly-magnetized neutron star atmospheres composed of mid-Z elements (carbon, oxygen and neon) with magnetic fields B=10^{12}-10^{13} G and effective temperatures Teff=(1-5)*10^6 K; this is done by first addressing the physics relevant to strongly-magnetized plasmas and calculating the equation of state and polarization-dependent opacities. We then obtain the atmosphere structure and spectrum by solving the radiative transfer equations in hydrostatic and radiative equilibrium. In contrast to hydrogen opacities at the relevant temperatures, mid-Z element opacities are dominated by numerous bound-bound and bound-free transitions. Consequently, temperature profiles are closer to grey profiles, and photosphere densities are lower than in the hydrogen case. Mid-Z element atmosphere spectra are significantly softer than hydrogen atmosphere spectra and show numerous absorption lines and edges. The atmosphere spectra depend strongly on surface composition and magnetic field but weakly on surface gravity. Absorption lines are primarily broadened by motional Stark effects and the (unknown) surface magnetic field distribution. Given the multiple absorption features observed from several isolated neutron stars, it is possible to determine, with existing X-ray data, the surface composition, magnetic field, temperature, and gravitational redshift; we present qualitative comparisons between our model spectra and the neutron stars 1E1207.4-5209 and RX J1605.3+3249. Future high-resolution X-ray missions such as Constellation-X will measure the gravitational redshift with high accuracy by resolving narrow absorption features, and when combined with radius measurements, it will be possible to uniquely determine the mass and radius of isolated neutron stars. (Abridged)