Quite simply, Mace believes in the rule of law. He does not think that the Jedi should unilaterally act against the Chancellor. We can see this trait in a few of his other defining moments. When Anakin joins the council, Mace says "You are on this council, but we do not grant you the rank of Master." His disapproval is obvious. To Mace, Anakin should have gone through the normal procedures, not merely skipped over them because of his prodigious talent with the Force.
Similarly, when the Jedi are discussing what to do if Palpatine does not lay down his emergency powers, Mace is concerned. After all, Palpatine promised that it would be a temporary situation.
Palpatine: The power you give me I will lay down when this crisis has abated.
However, even then, Mace sounds surprised when he responds to Ki Adi Mundi, saying "the Jedi Council would have to take power to ensure a peaceful transition." He seems to dislike the idea. Even then, it seems he only entertains it because Palpatine seemingly would be acting extralegally by retaining his dictatorial powers after the war was over, and the Council does seem to be legally empowered to arrest criminals in the name of the Senate.
If we need more evidence of this tendency, just look at this quote:
My name is General Mace Windu of the Jedi Order. At this point of the Clone War, I have dismantled and destroyed over 100,000 of you type one battle droids. I'm giving you an opportunity to peacefully lay down your weapons, so that you may be reprogrammed to serve a better purpose than spreading the mindless violence and chaos which you have inflicted upon the galaxy.
The Clone Wars, "Unfinished Business"
He is talking to an army of battle droids, who then proceed to blast him. Admittedly, his offer of forcibly reprogramming them is not terribly enlightened, but considering that most people in the Galaxy seem to think of droids as unworthy of any moral consideration, and that Windu knows full well that they are just going to try to shoot him anyway, this bespeaks a tremendous devotion to the procedures of war. Giving your enemy a chance to surrender is just the Way Things Are Done.
In short, Mace is committed to doing things according to protocol, or at least according to what he perceives as correct protocol. By all appearances, the Jedi have the right to arrest criminals, and conspiring against the Republic certainly qualifies; they do not, however, have the right to execute said malefactors.
However, between the moment that Mace declares his intent to arrest Palpatine and when he decides that he needs to kill him, a number of events happen that could easily have changed Mace's mind.
First, Palpatine has revealed to him that "I am the Senate!" Dooku had insinuated that hundreds of senators were under the influence of Sidious, but the Galactic Senate consists of thousands of delegates. Windu would have had great cause for concern, but he would likely have imagined that the "good" senators could outvote their treasonous brethren. Besides, influence could mean many things: it does not mean that they will always vote the way Palpatine wants. But by brazenly declaring himself to be synonymous with the Senate, Palpatine shows Windu that he has no fear of arrest, which means that his control goes further than merely having some sway over a few hundred people. Sure, Mace said "not yet," but that was more of a defiant retort. At this point, Mace is convinced: Palpatine cannot be fairly tried in the courts.
Further, Palpatine then demonstrates that he is personally a tremendous threat, and quite possibly all but impossible to keep contained long enough to expose his dirty deeds and convince the senators of his guilt, by killing three Jedi Masters in as many seconds, including the highly-skilled Kit Fisto, and nearly personally killing the fourth. That is why Mace says that Palpatine is "too dangerous to be left alive." He has just seen evidence that Palpatine is so powerful that he cannot effectively be imprisoned.
Palpatine's power in the dark side has also rattled Mace. He believes, probably correctly, that Palpatine's rule would be worse than he had assumed before. If he does not act now, he is convinced that the consequences will be dire. "The oppression of the Sith will never return."
Finally, Palpatine has just almost killed Mace. I would not count out the possibility that he is angry and desirous of vengeance.
