GJ 436b is a prime target for understanding warm Neptune exoplanet atmospheres and a target for multiple James Webb Space Telescope (JWST) Guaranteed Time Observation programs. Here, we report the first space-based optical transmission spectrum of the planet using two Hubble Space Telescope (HST) Space Telescope Imaging Spectrograph (STIS) transit observations from 0.53 to 1.03 {mu}m. We find no evidence for alkali absorption features, nor evidence of a scattering slope longward of 0.53 {mu}m. The spectrum is indicative of moderate to high metallicity (~100-1000x solar), while moderate-metallicity scenarios (~100x solar) require aerosol opacity. The optical spectrum also rules out some highly scattering haze models. We find an increase in transit depth around 0.8 {mu}m in the transmission spectra of three different sub-Jovian exoplanets (GJ 436b, HAT-P-26b, and GJ 1214b). While most of the data come from STIS, data from three other instruments may indicate this is not an instrumental effect. Only the transit spectrum of GJ 1214b is well fit by a model with stellar plages on the photosphere of the host star. Our photometric monitoring of the host star reveals a stellar rotation rate of 44.1 days and an activity cycle of 7.4 years. Intriguingly, GJ 436 does not become redder as it gets dimmer, which is expected if star spots were dominating the variability. These insights into the nature of the GJ 436 system help refine our expectations for future observations in the era of JWST, whose higher precision and broader wavelength coverage will shed light on the composition and structure of GJ 436b's atmosphere.