We have measured the beam-normal single-spin asymmetry An in the elastic scattering of 1-3 GeV transversely polarized electrons from H-1 and for the first time from He-4, C-12, and Pb-208. For H-1, He-4, and C-12, the measurements are in agreement with calculations that relate A(n) to the imaginary part of the two-photon exchange amplitude including inelastic intermediate states. Surprisingly, the Pb-208 result is significantly smaller than the corresponding prediction using the same formalism. These results suggest that a systematic set of new A(n) measurements might emerge as a new and sensitive probe of the structure of heavy nuclei.