tl;dr: Arpaio was sentenced for violating a court order, which ordered him to stop violating the law. In this case, a presidential pardon takes away any recourse the judiciary has, thus circumventing the separation of powers and thus the rule of law.
Few people claim that the pardon was illegal. What people mean by "rule of law" in this case is that it was against the unwritten, but well established, procedure of pardons and an attack against the separation of powers.
Procedures and Reasons for Pardons
Specifically, the pardon violated - not legally binding - procedures because:
- Trump did not consult anyone at the Justice Department
- Arpaio did not request a pardon
- Arpaio was not sentenced yet
Additionally, the pardon is generally applied when one or more of these points apply:
- Facts of the case have changed
- The individual shows regret
- The individual served their sentence
- The sentence is seen as too harsh or unjust (compared to how it was seen when issued)
None of those is the case here. Arpaio is proud of his racist and criminal behavior, and wasn't sentenced yet, so nothing has changed since his sentencing.
Because of this, the pardon is perceived not as righting a previous wrong, or as mercy for a person showing regret, but as going over a judge.
Separation of Powers and the rule of law
In many democracies, state powers are separated into Legislative, Executive, and Judicial powers.
Rule of law specifically means:
the legal principle that law should govern a nation, as opposed to being governed by decisions of individual government officials. It primarily refers to the influence and authority of law within society, particularly as a constraint upon behaviour, including behaviour of government officials.
While the pardon itself may have been legal, Trump circumvented the checks the judiciary could exercise over the executive (of which Arpaio was a part of). The law that prevented Arpaio from his illegal activities can be considered bypassed; It wasn't the law that governed, but Arpaio. Trumps pardon of him - without any sign of guilt or wrongdoing - is a support of Arpaio's ignorance of the law, and thus in conflict with the principal of rule of law.
Martin Redish shows in the NYT why this pardon is an attack on the existing process, the separation of power, and thus the rule of law:
This is uncharted territory. Yes, on its face the Constitution’s pardon power would seem unlimited. [...] But the Arpaio case is different: The sheriff was convicted of violating constitutional rights, in defiance of a court order involving racial profiling. Should the president indicate that he does not think Mr. Arpaio should be punished for that, he would signal that governmental agents who violate judicial injunctions are likely to be pardoned, even though their behavior violated constitutional rights, when their illegal actions are consistent with presidential policies.
Many legal scholars argue that the only possible redress is impeachment — itself a politicized, drawn-out process. But there may be another route. If the pardon is challenged in court, we may discover that there are, in fact, limits to the president’s pardon power after all. [...]
[I]f the president signals to government agents that there exists the likelihood of a pardon when they violate a judicial injunction that blocks his policies, he can all too easily circumvent the only effective means of enforcing constitutional restrictions on his behavior. Indeed, the president could even secretly promise a pardon to agents if they undertake illegal activity he desires. [...]
[I]f the president can employ the pardon power to circumvent constitutional protections of liberty, there is very little left of the constitutional checks on presidential power.
Noah Feldman argues the same on Bloomberg:
This is the crime that Trump is suggesting he might pardon: willful defiance of a federal judge’s lawful order to enforce the Constitution.
It’s one thing to pardon a criminal out of a sense of mercy or on the belief that he has paid his debt to society. It’s trickier when the president pardons someone who violated the law in pursuit of governmental policy [...]
But it would be an altogether different matter if Trump pardoned Arpaio for willfully refusing to follow the Constitution and violating the rights of people inside the U.S.
Such a pardon would reflect outright contempt for the judiciary, which convicted Arpaio for his resistance to its authority. Trump has questioned judges’ motives and decisions, but this would be a further, more radical step in his attack on the independent constitutional authority of Article III judges.
An Arpaio pardon would express presidential contempt for the Constitution. [...] Fundamentally, pardoning Arpaio would also undermine the rule of law itself.
Additional reasons for outrage and meaning for future investigations
Most of the outrage is of course not (only) because of the contempt for the rule of law, but because this isn't the first time Trump has shown his support for racists and white supremacists. And even those that agree with Trumps endorsement of white supremacists might agree that Arpaio was not a very decent person by any definition.
Paul Krugman argues along those lines in an opinion piece in the NYT. He also gives an overview over Arpaios conviction and how this pardon might affect future investigations (and thus again attack the rule of law):
Joe Arpaio engaged in blatant racial discrimination. His officers systematically targeted Latinos, often arresting them on spurious charges and at least sometimes beating them up when they questioned those charges. [...]
Once Latinos were arrested, bad things happened to them. Many were sent to Tent City, which Arpaio himself proudly called a “concentration camp,” [...]
And when he received court orders to stop these practices, he simply ignored them, which led to his eventual conviction — after decades in office — for contempt of court [...]
Arpaio is, of course, a white supremacist. [...]
Trump’s motives are easy to understand. For one thing, Arpaio, with his racism and authoritarianism, really is his kind of guy. For another, the pardon is a signal to those who might be tempted to make deals with the special investigator as the Russia probe closes in on the White House: Don’t worry, I’ll protect you. [...]