We study the applicability of several galaxy environment measures (n^th-nearest-neighbor distance, counts in an aperture, and Voronoi volume) within deep redshift surveys. Mock galaxy catalogs are employed to mimic representative photometric and spectroscopic surveys at high redshift (z ~ 1). We investigate the effects of survey edges, redshift precision, redshift-space distortions, and target selection upon each environment measure. We find that even optimistic photometric redshift errors (σ_z = 0.02) smear out the line-of-sight galaxy distribution irretrievably on small scales; this significantly limits the application of photometric redshift surveys to environment studies. Edges and holes in a survey field dramatically affect the estimation of environment, with the impact of edge effects depending upon the adopted environment measure. These edge effects considerably limit the usefulness of smaller survey fields (e.g. the GOODS fields) for studies of galaxy environment. In even the poorest groups and clusters, redshift-space distortions limit the effectiveness of each environment statistic; measuring density in projection (e.g. using counts in a cylindrical aperture or a projected n^th-nearest-neighbor distance measure) significantly improves the accuracy of measures in such over-dense environments. For the DEEP2 Galaxy Redshift Survey, we conclude that among the environment estimators tested the projected n^th-nearest-neighbor distance measure provides the most accurate estimate of local galaxy density over a continuous and broad range of scales. Comment: 17 pages including 16 figures, accepted to ApJ