The gemara says that when Hashem commanded Shaul to wipe out Amalek, he made a kal v'chomer that if an egla arufa is brought for one life, how can he take so many lives. Furthermore, even if the people deserve to be killed, what did the animals do! A bas kol went out and said אל תהי צדיק הרבה. The exact opposite happened when Shaul killed out the entire city of Kohanim, Nov. A bas kol went out and said אל תרשע הרבה. The gemara continues to explain that Shaul only did one aveira and that caused him to lose the throne, whereas Dovid did more aveiros and did not lose the throne. The gemara considers the aveira of Shaul to be the ma'aseh with Agag, not killing amalek. Even though he also sinned by killing out Nov, that didn't count in why he lost the malchus, because it was already lost from before.
The concept behind this gemara seems to be very similar to what we find by Yosef. In parshas vayigash, when Yosef finally reveals himself, he questions whether his father is still alive. The Beis Haleivi has a fascinating essay where he explains based on a Midrash - אוי לנו ליום הדין, that Yosef was giving them very sharp mussar. The claim that the brothers were making throughout all their discussions with Yosef is that they feared the health of their elderly father Yaakov and that was their primary concern. By Yosef revealing himself, he was essentially undermining all their arguments. Had they truly been concerned for Yaakov, they would never have sold him which caused Yaakov 22 years of extreme grief and suffering. The revelation of Yosef was done in the format of אני יוסף העוד אבי חי - "I am Yosef, Is my father still alive", meaning, could my father have tolerated the suffering that you caused him all these years. Yosef was able to show that all their arguments until now which seemed very legitimate, were all a smokescreen and not their true intent.
Shaul claimed to have spared the women and animals of amalek due to his compassionate nature. However, the ruthless murder of the kohanim in Nov indicated that he was not a man of compassion, thereby undermining any excuse he may have had for not killing amalek. That is the intent of the gemara, אל תהי צדיק הרבה and אל תרשע הרבה, because the latter event undermined his justification for the earlier one.
If Shaul was not truly motivated by compassion, why then did he kill out the city of Nov? The gemara says at the bottom of the daf - מפני מה נענש שאול? מפני שמחל על כבודו, referring to the story of nachash ha'amoni, not willing to kill those who rebelled agains him. Rashi seems bothered by the question of the gemara, because the gemara already established that the reason Shaul lost his throne was because of the ma'aseh agag, not killing amalek. Therefore, Rashi explains what caused him to come to the action that was the reason for losing his throne. Meaning, what midah caused the problem? The midah of misplaced humility, being mochel on his kavod when as a king he must uphold his honor and instill אימה over the people. שום תשים עליך מלך - שתהא אימתו עליך, is the reason that a king can't be mochel. This was the midah that caused Shaul to lack the confidence and be scared to assert himself in killing out the entire nation of amalek. The midah of humility is generally good, but a king can't display himself as humble and unassertive. The Tosafos Yeshanim explains that this is what Rav Nachman meant when he said that Shaul was like a one day old child - שמלוכלך בטיט ובצואה, filthy in his excrement. He meant to say that Shaul was an extremely humble person. The Tosafos Yeshanims struggles with why he was punished (by being scared through mal'achim) for saying this, since it was a compliment. It seems that the answer is, that although it was a compliment in terms of Shaul's personality and character traits, it is an inappropriate midah for a king to display publicly.