The gemara quotes a braisa which has a machlokes regarding the legitimacy of appointing a king. R. Yehuda says that it is one of the 3 mitzvos that the Jews had when they entered E.Y. However, R. Nehorai says: לא נאמרה פרשה זו אלא כנגד תרעומתן. Rashi explains that R. Nehorai argues on R. Yehuda and holds that the "mitzvah" of appointing a king was never said as a mitzvah, and was never meant to be an ideal. The only reason that Hashem permitted the appointing of a king is to preempt the complaints of the Jews who would ask for a king. Finally, the third opinion is that of R. Eliezer who holds that the zekainim asked properly since they were looking for an authority to enforce the law, but the amei ha'aretz asked improperly since they were looking for someone to help them conquer land from their enemies.
Based on Rashi's understanding that R. Yehuda holds it is a mitzva, and R. Nehorai disagrees; if we were to pasken like R. Yehuda, we couldn't hold like R. Nehorai. However, the Rambam seems to have a different approach. The Rambam (Hil. Melachim 1:1-2) writes that there are 3 mitzvos when the Jews enter E.Y., to set up a king, destroy amalek, and build the beis hamikdash. The Rambam holds like R. Yehuda that there is a mitzvah to set up a king. Yet, the Rambam writes at the end of Halacha 2:
מאחר שהקמת המלך מצוה למה לא רצה הקב"ה כששאלו מלך משמואל? לפי ששאלו בתרעומת ולא שאלו לקיים המצוה אלא מפני שקצו בשמואל הנביא שנאמר כי לא אותך מאסו כי אותי מאסו
As the Radvaz points out, the Rambam seems to be paskening like R. Nehorai that the king was a result of תרעומת - complaints. How does the Rambam fit R. Yehuda together with R. Nehorai? He holds that even according to R. Nehorai there is a mitzvah to have a king but the intentions were bad. They should have been asking for a king with the intent of doing the mitzvah, but instead they wanted a king as a complaint about their present situation.
The Ran in his Drashos has a beautiful approach to the issue. He explains that there is a separation of powers between the judicial branch who were assigned with judging din torah, and the executive (king) branch that were assigned with maintaining law and order. They wanted a king who would fill the role of the "shofeit". They were looking to replace din torah (judged by the shofeit) which brings about השראת השכינה, with secular law that only serves the purpose of maintaining law and order. Their sin was in requesting: תנה לנו מלך לשפטנו. The king was meant to compliment the shofeit and fill in the gaps where the Torah acquits and he must be גודר גדר and convict to maintain law and order. The king was never meant to substitute din torah.