One of the leading theories about this sort of thing (rule of law) has to do with the development of democratic politics. North and Weingast ("Constitutions and Commitment: The Evolution of Institutions Governing Public Choice in Seventeenth-Century England") have a wonderful discussion. One of the primary problem in Stuart England was that the king was terrible at paying off debts (he was the sovereign, what could lenders do?). He would also force lenders to "loan" him money. All of this was causing a lot of strife. North and Weingast talk about how this was one of the things that the development of independent courts (through the development of common law) and parliament were a response to this problem, and a means of constraining the king in a way that would be credible (notoriously difficult to do). This, in turn, led to the development of a certain form of rule of law, whereby even the king was subject to certain constraints. And it stuck because it led to interest rates for the monarch going down a lot, so the king actually ended up better off as well.

There's also an excellent book by Acemoglu and Robinson on this subject (Why Nations Fail). Essentially, they argue that once you do have a relatively broad base in control of political power, as with parliament, then you will have an easier time establishing rule of law. If you let others violate the law (against someone else), then you are just setting a poor precedent for the future, when they may turn on you. So people who want to avoid predation will not want to set this precedent. The nobility could do this back in the day, but the people often could not because they lacked the political power to have any say in these decisions in the first place. Until parliament came along.

My understanding is that early English criminal law was administered by felony judges who rode circuit around the country (the "assizes"); the specific conduct of assizes is a little beyond my expertise, but I believe this is what you are describing when you say the king/lord held court to hear grievances.

Your broader question, "how did arbitrary justice give way to more fair legal systems," is very broad indeed, but more up my alley. I'll try to speak to it by giving some examples.

First, when you talk about codified and fair legal processes, what you're really talking about is the broad concept of "due process," or more specifically, "procedural due process." That is, the notion that anyone in court is entitled to a fair procedure, and may only be deprived of a right upon notice and an opportunity to be heard on the matter.

"Notice and opportunity to be heard" is the civil formulation; it means you can't have your social security benefits canceled on a whim. See Mathews v. Eldridge, 424 U.S. 319 (1976). In the criminal context, American due process is measured less against that flexible notion, and more against the specific procedural rights conferred by the Bill of Rights and other authorities. See Medina v. California, 505 U.S. 437, 443, 446 (1992) (due process defined by, and should not be expanded under, the “open-ended rubric of the Due Process Clause”). For example, the Bill of Rights requires that at a criminal trial, you have the right to confront your accusers (Sixth Amendment), and against self-incrimination (Fifth Amendment).

There is a view of history where these rights are specific reactions against specific, perceived ills of the British criminal justice system. When we speak about the "confrontation clause," for example, judges invoke the problem it was intended to remedy: "star chamber" prosecutions where criminal defendants were tried on the basis of hearsay, and convicted without being able to face or question their accusers. In one of the seminal "confrontation clause" cases in American law, Crawford v. Washington, 541 U.S. 36 (2004), the Supreme Court referred one such trial, the trial and conviction of Sir Walter Raleigh, as an example that influenced the drafting (and therefore the meaning) of the Sixth Amendment.

The most notorious instances of civil-law examination occurred in the great political trials of the 16th and 17th centuries. One such was the 1603 trial of Sir Walter Raleigh for treason. Lord Cobham, Raleigh’s alleged accomplice, had implicated him in an examination before the Privy Council and in a letter. At Raleigh’s trial, these were read to the jury. Raleigh argued that Cobham had lied to save himself: “Cobham is absolutely in the King’s mercy; to excuse me cannot avail him; by accusing me he may hope for favour.” Suspecting that Cobham would recant, Raleigh demanded that the judges call him to appear, arguing that “[t]he Proof of the Common Law is by witness and jury: let Cobham be here, let him speak it. Call my accuser before my face . . . .” The judges refused, and, despite Raleigh’s protestations that he was being tried “by the Spanish Inquisition,” the jury convicted, and Raleigh was sentenced to death.

Slip opinion at 44. What this exemplifies is that the criminal law became "fair" only by fits and starts. There was no watershed moment where due process spontaneously came into being; instead, modern criminal procedure is the result of the accretion of precedent over hundreds of years, made real in some cases by the Constitution and state law.

Another thing you might be interested in is that American separation of powers theory specifically rebukes the notion of "common law crimes"; that is, crimes defined by the judiciary. Instead, all criminal law (with the exception of treason, which is constitutional) is by necessity statutory, to avoid a situation where the judiciary both makes and enforces the law. See United States v. Hudson, 11 U.S. 32 (1812). Modern criminal law is informed by the common law, but only where relevant within the four corners of the statute.

I think we tend to assume that early English law was more arbitrary than it actually was. It makes for better television that way. But in medieval and early modern England, the king couldn't just say "off with his head." Take Henry VIII as an example--he had to go through the forms of law to get anyone executed. Even Anne Boleyn was convicted by a jury (in her case, because she was a peer, it was a jury of her fellow lords). Trial by jury was enshrined in English law by the thirteenth century. Juries were struck for all felony trials, whether they were local trials (administered by the assize court justices, riding on circuit) or trials at the high courts in Westminster. There was only one way to get someone executed without a jury trial--that was through an act of attainder. An act of attainder was basically an act of parliament convicting someone without trial. Under the U.S. Constitution, Congress cannot pass acts of attainder, so in an American context this particular form of judicial tyranny was outlawed in 1789. But it was never actually outlawed in the UK, although it fell into disuse after the late eighteenth century (Winston Churchill briefly considered reviving it to prosecute Nazi war criminals without trial). When English kings did try to exercise summary justice, they encountered enormous popular resistance. A good example is the debacle of King Charles I's forced loan of 1626-1627. The loan was very unpopular, and even more unpopular was the fact that Charles sent five knights to prison for failing to lend him money without charging them or bringing them to trial. The five knights were subsequently released without suffering any penalties, but many members of parliament felt that the king had behaved unjustly. This led ultimately to the Petition of Right of 1628, which reaffirmed that the king could not imprison anyone without bringing them to trial, and that parliament had to authorize all taxes. That said, there may have been other countries where the monarch could simply say "off with his head" and it would be done without a trial (summary justice). I'm not an expert on Russian history, but my impression is that Ivan the Terrible did this sort of thing. Or perhaps that is a historical myth as well?