We calculate photometric redshifts from the Sloan Digital Sky Survey Main Galaxy Sample, The Galaxy Evolution Explorer All Sky Survey, and The Two Micron All Sky Survey using two new training-set methods. We utilize the broad-band photometry from the three surveys alongside Sloan Digital Sky Survey measures of photometric quality and galaxy morphology. Our first training-set method draws from the theory of ensemble learning while the second employs Gaussian process regression both of which allow for the estimation of redshift along with a measure of uncertainty in the estimation. The Gaussian process models the data very effectively with small training samples of approximately 1000 points or less. These two methods are compared to a well known Artificial Neural Network training-set method and to simple linear and quadratic regression. We also demonstrate the need to provide confidence bands on the error estimation made by both classes of models. Our results indicate that variations due to the optimization procedure used for almost all neural networks, combined with the variations due to the data sample, can produce models with variations in accuracy that span an order of magnitude. A key contribution of this paper is to quantify the variability in the quality of results as a function of model and training sample. We show how simply choosing the ``best" model given a data set and model class can produce misleading results. We also investigate supplemental information provided by the Sloan Digital Sky Survey photometric pipeline related to photometric quality and galaxy morphology tracers. We show that, using these additional quality and morphology indicators rather than only the Sloan Digital Sky Survey broad-band u,g,r,i,z imaging data commonly used, one can improve redshift accuracy by 10s of percent. Near Infrared LaTeX broad-band photometry provided from the Two Micron All Sky Survey and near-ultraviolet and far-ultraviolet broad-band data from The Galaxy Evolution Explorer All Sky Survey are also investigated where they overlap with the Sloan Digital Sky Survey. Our results show that robust photometric redshift errors as low as 0.02 RMS can regularly be obtained. We believe these can be expanded to other photometric surveys where sufficient redshift calibration objects exist.