Heterolithic, boulder-containing, pebble-strewn surfaces occur along the lower slopes of Aeolis Mons ("Mt. Sharp") in Gale crater, Mars. They were observed in HiRISE images acquired from orbit prior to the landing of the Curiosity rover. The rover was used to investigate three of these units named Blackfoot, Brandberg, and Bimbe between sols 1099 and 1410. These unconsolidated units overlie the lower Murray formation that forms the base of Mt. Sharp, and consist of pebbles, cobbles and boulders. Blackfoot also overlies portions of the Stimson formation, which consists of eolian sandstone that is understood to significantly postdate the dominantly lacustrine deposition of the Murray formation. Blackfoot is elliptical in shape (62 × 26 m), while Brandberg is nearly circular (50 × 55 m), and Bimbe is irregular in shape, covering about ten times the area of the other two. The largest boulders are 1.5-2.5 m in size and are interpreted to be sandstones. As seen from orbit, some boulders are light-toned and others are dark-toned. Rover-based observations show that both have the same gray appearance from the ground and their apparently different albedos in orbital observations result from relatively flat sky-facing surfaces. Chemical observations show that two clasts of fine sandstone at Bimbe have similar compositions and morphologies to nine ChemCam targets observed early in the mission, near Yellowknife Bay, including the Bathurst Inlet outcrop, and to at least one target (Pyramid Hills, Sol 692) and possibly a cap rock unit just north of Hidden Valley, locations that are several kilometers apart in distance and tens of meters in elevation. These findings may suggest the earlier existence of draping strata, like the Stimson formation, that would have overlain the current surface from Bimbe to Yellowknife Bay. Compositionally these extinct strata could be related to the Siccar Point group to which the Stimson formation belongs. Dark, massive sandstone blocks at Bimbe are chemically distinct from blocks of similar morphology at Bradbury Rise, except for a single float block, Oscar (Sol 516). Conglomerates observed along a low, sinuous ridge at Bimbe consist of matrix and clasts with compositions similar to the Stimson formation, suggesting that stream beds likely existed nearly contemporaneously with the dunes that eventually formed the Stimson formation, or that they had the same source material. In either case, they represent a later pulse of fluvial activity relative to the lakes associated with the Murray formation. These three units may be local remnants of infilled impact craters (especially circular-shaped Brandberg), decayed buttes, patches of unconsolidated fluvial deposits, or residual mass-movement debris. Their incorporation of Stimson and Murray rocks, the lack of lithification, and appearance of being erosional remnants suggest that they record erosion and deposition events that post-date the exposure of the Stimson formation.