What is the Chidush that they did not bring a gift to him?
Radak: The custom was to bring a gift to the king on the day he was established to be king.
Radak citing Targum Yonasan: They did not come to give to him Shalom.
Why were they dissatisfied with Sha'ul?
Malbim: Most of the nation wanted a king who will cast off the yoke of Torah, "Leshafteinu k'Chol ha'Goyim" (8:5), i.e. to lead them according to Nochri laws. After they saw that he clings to fear of Hashem, and will go in it all days, they saw that he will not fulfill their desire. 1
Malbim (8:19) says that after Shmuel told them Mishpat ha'Melech, they retracted and requested a Melech who must conduct like Torah law! Perhaps a minority did not retract. However, the verse implies that they rejected him because they thought that he cannot save them! (PF)
