We report the detection of UCF-1.01, a strong exoplanet candidate with a radius 0.66 +/- 0.04 times that of Earth (R_{oplus}). This sub-Earth-sized planet transits the nearby M-dwarf star GJ 436 with a period of 1.365862 +/- 8x10^{-6} days. We also report evidence of a 0.65 +/- 0.06 R_{oplus} exoplanet candidate (labeled UCF-1.02) orbiting the same star with an undetermined period. Using the Spitzer Space Telescope, we measure the dimming of light as the planets pass in front of their parent star to assess their sizes and orbital parameters. If confirmed, UCF-1.01 and UCF-1.02 would be called GJ 436c and GJ 436d, respectively, and would be part of the first multiple-transiting-planet system outside of the Kepler field. Assuming Earth-like densities of 5.515 g/cm^3, we predict both candidates to have similar masses (~0.28 Earth-masses, M_{oplus}, 2.6 Mars-masses) and surface gravities of ~0.65 g (where g is the gravity on Earth). UCF-1.01s equilibrium temperature (T_{eq}, where emitted and absorbed radiation balance for an equivalent blackbody) is 860 K, making the planet unlikely to harbor life as on Earth. Its weak gravitational field and close proximity to its host star imply that UCF-1.01 is unlikely to have retained its original atmosphere; however, a transient atmosphere is possible if recent impacts or tidal heating were to supply volatiles to the surface. We also present additional observations of GJ 436b during secondary eclipse. The 3.6-micron light curve shows indications of stellar activity, making a reliable secondary eclipse measurement impossible. A second non-detection at 4.5 microns supports our previous work in which we find a methane-deficient and carbon monoxide-rich dayside atmosphere.