For me, it is definitely the idea that there is no one single morality that holds for all people. This is something that seems a bit abhorrent (largely because we know that Nietzsche's ideas helped give rise to Nazism). However, it is very important to our understanding of history and of the history of ideas.
I am not sure it is entirely easy to identify one critical issue that comes out of Nietzsche's work. I do think that one of the most important concepts or lessons to emerge is the contingency of morality and how this structure invades consciousness. For so long, the notion of a permanence to morality, a type of transcendent structure that is absolutist in its approach to how humans behave, was something that was completely accepted and not very scrutinized. I think that Nietzsche does a good job in suggesting that there are vocabularies that are temporal, emerging at certain points in consciousness and helpful in defining morality and what constitutes moral behavior. Regardless of whether one embraces this, I think that the practice of assessing the contingency of morality is something vitally important. This is more along the lines of understanding the changing and the fluid dynamic of how social orders construct morality. Even in the midst of absolutist belief, there has been a contingency attached to morality and how societies view it, and in this, one of the strongest lessons of Nietzsche's work develops. The very idea of morality as a "genealogy," or something that has grown and developed in a changing context over time is where some of Nietzsche's lessons in the philosophical text are the strongest.
It is the lesson that morality is not fixed or destined by God. Rather it comes from the formation of society and is constantly evolving through the social changes/ power dynamics in society. We really need to go back to the history to find out the source or morality, rather than taking it for granted.