  (abridged) We present an analysis of high resolution optical spectra for a
sample of very young, mid- to late M, low-mass stellar and substellar objects
in Upper Sco and Taurus. Effective temperatures (T_eff) and surface gravities
are derived from a multi-feature spectral analysis using TiO, NaI and KI,
through comparison with the latest synthetic spectra. In combination, they
allow us to determine T_eff to within 50K and gravity to within 0.25 dex. Our
high-resolution analysis does not require extinction estimates. Moroever, it
yields T_eff and gravities independent of theoretical evolutionary models. We
find that our gravities for most of the sample agree remarkably well with the
isochrone predictions for the likely cluster ages. However, discrepancies
appear in our coolest targets: these appear to have significantly lower gravity
(by up to 0.75 dex) than our hotter objects, even though our entire sample
covers a relatively narrow range in T_eff (about 300K). This drop in gravity is
also implied by inter-comparisons of the data alone, without recourse to
synthetic spectra. We consider, and argue against, dust opacity, cool stellar
spots or metallicity differences leading to the observed spectral effects; a
real decline in gravity is strongly indicated. Such gravity variations are
contrary to the predictions of the evolutionary tracks, causing improbably low
ages to be inferred from the tracks for our coolest targets. We venture that
these results may arise from evolutionary model uncertainties related to
accretion, deuterium-burning and/or convection effects. Finally, when combined
with photometry and distances, our technique for deriving gravities and
temperatures provides a way of obtaining masses and radii for substellar
objects independent of evolutionary models, as presented in Paper II.
