Ground-state structures and other experimentally relevant isomers of Au(15) (-) to Au(24) (-) clusters are determined through joint first-principles density functional theory and photoelectron spectroscopy measurements. Subsequent calculations of molecular O(2) adsorption to the optimal cluster structures reveal a size-dependent reactivity pattern that agrees well with earlier experiments. A detailed analysis of the underlying electronic structure shows that the chemical reactivity of the gold cluster anions can be elucidated in terms of a partial-jellium picture, where delocalized electrons occupying electronic shells move over the ionic skeleton, whose geometric structure is strongly influenced by the directional bonding associated with the highly localized "d-band" electrons.