Listening habits are strongly influenced by two opposing aspects, the desire for variety and the demand for uniformity in music. In this work we quantify these two notions in terms of musical instrumentation and production technologies that are typically involved in crafting popular music. We assign a "complexity value" to each music style. A style is complex if it shows the property of having both high variety and low uniformity in instrumentation. We find a strong inverse relation between variety and uniformity of music styles that is remarkably stable over the last half century. Individual styles, however, show dramatic changes in their "complexity" during that period. Styles like "new wave" or "disco" quickly climbed towards higher complexity in the 70s and fell back to low complexity levels shortly afterwards, whereas styles like "folk rock" remained at constant high complexity levels. We show that changes in the complexity of a style are related to its number of sales and to the number of artists contributing to that style. As a style attracts a growing number of artists, its instrumentational variety usually increases. At the same time the instrumentational uniformity of a style decreases, i.e. a unique stylistic and increasingly complex expression pattern emerges. In contrast, album sales of a given style typically increase with decreasing complexity. This can be interpreted as music becoming increasingly formulaic once commercial or mainstream success sets in.