The novelisation has a very slightly different version of the conversation with Windu and Palpatine. It would appear that their stated reason for arresting him was flawed, hence their arrest procedure was flawed since you can't just arrest someone for their religious beliefs in the Republic.
PALPATINE: I beg your pardon? What I am? When last I checked, I was Supreme Chancellor of the Republic you are sworn to serve. I hope
I misunderstand what you mean by custody, Master Windu. It smacks of
MACE WINDU: You’re under arrest.
PALPATINE: Really, Master Windu, you cannot be serious. On what charge?
MACE WINDU: You’re a Sith Lord!
PALPATINE: Am I? Even if true, that’s hardly a crime. My philosophical outlook is a personal matter. In fact-the last time I
read the Constitution, anyway-we have very strict laws against this
type of persecution. So I ask you again: what is my alleged crime? How
do you expect to justify your mutiny before the Senate? Or do you
intend to arrest the Senate as well?
Revenge of the Sith: Official Novelisation
That being said, they also have evidence (from Anakin's testimony about Palpatine's admission) that Palpatine has been consorting with the enemy, so their decision to confront him was entirely valid. He's been committing treason and their intention was to arrest him for trial by the Senate rather than simply assassinating him.
MACE WINDU: In the name of the Galactic Senate of the Republic, you are under arrest, Chancellor.
MACE WINDU and the other JEDI ignite their lightsabers.
PALPATINE: Are you threatening me, Master Jedi?
MACE: The Senate will decide your fate.
RotS: Original Screenoplay
Without having a copy of the Republic Code of Justice in front of us, we can be reasonably certain that any decisions made in this matter would be political in nature, rather than being decided by recourse to the criminal courts, but their decision to arrest him immediately was a valid and proportionate one (and entirely legal), given the immediacy of his contact with the enemy and the severity of his crimes.