I think some of the best solos are those that are very melodic but are difficult to play. Like when you're trying to learn a really good solo off a CD that seems simple, until one little part in it has you scratching your head wondering how the heck the guy did it.
Its like, the guy knows how to shred but he's resisting the temptation to do it just for sake of doing it.