You've said that the most important thing to do when designing a CD cover is to catch someone's attention. But that's not always easy. One simple rule of attention-grabbing is to do something that everyone else is not. If you look at any music genre there are things that everyone does. On every rap album, the artist has a gold ring, a gold chain, a certain hand movement, and looks angry.
Every alternative album has a picture of a chain saw lying out of focus on green grass.
Every heavy metal is black with a vaguely Nazi typeface and some howling wolf on the side. Staying within those cliches is a sure path to being overlooked. The first thing we do is meet with the band, usually before we've listened to the music. We ask what's the story of the album, how they wrote it, and what's the mood of the music. At our first meeting, I try to avoid talking about the cover itself.