We present X-ray, UV/optical, and radio observations of the stripped-envelope, core-collapse supernova (SN) 2011ei, one of the least luminous SNe IIb or Ib observed to date. Our observations begin with a discovery within 1 day of explosion and span several months afterward. Early optical spectra exhibit broad, Type II-like hydrogen Balmer profiles that subside rapidly and are replaced by Type Ib-like He-rich features on the timescale of one week. High-cadence monitoring of this transition suggests that absorption attributable to a high velocity (> 12,000 km/s) H-rich shell is not rare in Type Ib events. Radio observations imply a shock velocity of v = 0.13c and a progenitor star mass-loss rate of 1.4 x 10^{-5} Msun yr^{-1} (assuming wind velocity v_w=10^3 km/s). This is consistent with independent constraints from deep X-ray observations with Swift-XRT and Chandra. Overall, the multi-wavelength properties of SN 2011ei are consistent with the explosion of a lower-mass (3-4 Msun), compact (R* <= 1x10^{11} cm), He core star. The star retained a thin hydrogen envelope at the time of explosion, and was embedded in an inhomogeneous circumstellar wind suggestive of modest episodic mass-loss. We conclude that SN 2011ei's rapid spectral metamorphosis is indicative of time-dependent classifications that bias estimates of explosion rates for Type IIb and Ib objects, and that important information about a progenitor star's evolutionary state and mass-loss immediately prior to SN explosion can be inferred from timely multi-wavelength observations.