I've been thinking more about explaining what we mean by "insulators", in light of some of the insightful comments. As I'd said, we can think about three major classes of insulators: band insulators (a large gap due to single-particle effects (more below) exists in the ladder of electronic states above the highest occupied state); Anderson insulators (the highest occupied electronic states are localized in space, rather than extending over large distances; localization happens because of disorder and quantum interference); and Mott insulators (hitherto neglected electron-electron interactions make the energetic cost of moving electrons prohibitively high).
The idea of an energy gap (a big interval in the ladder of states, with the states below the gap filled and the states above the gap empty) turns out to be a unifying concept that can tie all three of these categories together. In the band insulator case, the states are pretty much single-particle states (that is, the energy of each state is dominated by the kinetic energies of single electrons and their interactions with the ions that supply the electrons). In the Anderson insulator case, the gap is really the difference in energy between the highest occupied state and the nearest extended state (called the mobility edge). In the Mott case, the states in question are many-body states that have a major contribution due to electron-electron interactions. The electron-electron interaction cost associated with moving electrons around is again an energy gap (a Mott gap), in the ladder of many-body (rather than single-particle) states.
I could also turn this around and talk in terms of the local vs. extended character of the highest occupied states (as Peter points out). In the ideal (infinite periodic solid) band insulator case, all (single-particle) electronic states are extended, and it's the particular lattice arrangement and electronic population that determines whether the highest occupied state is far from the nearest unoccupied state. In the Anderson case, quantum interference + disorder leads to the highest occupied states looking like standing waves - localized in space. In the Mott case, it's tricky to try to think about many-body states in terms of projections onto single-particle states, but you can do so, and you again find that the highest relevant states are localized (due, it turns out, to interactions). Like Peter, I also have been meaning to spend more time thinking hard about insulators.
Coming soon: a discussion of "metals".