In my view, Oliver Wendell Holmes is one of the most overrated justices ever to sit on the Supreme Court, and H.L. Mencken's contemporary critique of Holmes, linked by co-blogger David Bernstein, is a good explanation of why. As Mencken put it, Holmes was no "advocate of the rights of man," but rather "an advocate of the rights of lawmakers." With rare exceptions, he ruled that legislators could do almost anything they wanted, even if it violated the plain text of the Constitution, or the original meaning. Mencken accurately points out that under Holmes' judicial philosophy, "there would be scarcely any brake at all upon lawmaking, and the Bill of Rights would have no more significance than the Code of Manu."
Progressive contemporaries and later liberals defended Holmes because he upheld economic regulations against challenges under the Fourteenth Amendment. But he also deferred to the legislature in upholding forcible sterilization in Buck v. Bell (the famous "three generations of imbeciles is enough" case), and also dissented in landmark civil rights cases such as the peonage cases (which helped prevent southern blacks from being dragooned back into a forced labor system). As Mencken points out, Holmes also upheld fairly egregious restrictions of First Amendment rights during World War I and at other times. His reputation as a free speech civil libertarian mostly rests on a few instances where he deviated from his general pattern.
Perhaps Holmes' ultradeferential jurisprudence could be defended if it were compelled by the text or original meaning of the Constitution. In reality, however, many of his decisions went directly against the text and purpose of the constitutional provision in question. For example, he voted to uphold racially restrictive zoning and peonage laws despite the fact that the Fourteenth Amendment was clearly intended to forbid government-mandated racial discrimination in property and contract rights, and voted to uphold peonage laws despite the plain text of the Thirteenth Amendment, which unequivocally forbids "involuntary servitude."
One could also defend Holmes on the ground that he was merely a product of his times. On many of these issues, however, he was actually in dissent, which suggests that he wasn't merely reflecting the consensus view of the day.
Finally, one could respect Holmes more if he upheld these abhorrent laws despite his personal distaste for them. In many of these cases, however, he either approved of the laws in question or was indifferent to them. His enthusiasm for mandatory sterilization in Buck v. Bell is well-known. But he was also indifferent to or mildly supportive of even very extreme segregation laws, and various harsh restrictions on freedom of speech and press. More generally, Holmes was a kind of Social Darwinist of the political process who believed that majority rule was a force of nature that must almost always be deferred to.
It is understandable that early 20th century Progressives admired Holmes. In addition to supporting expanded government control of the economy, many of them also supported eugenics, restrictions on civil liberties, and government-mandated segregation (seen as a way of promoting social order and preventing the white race from being swamped by "inferior" groups). Even those inclined to be sympathetic to African-American rights or freedom of speech tended to subordinate these causes to what they considered to be the more important objectives of increasing government economic regulation and strengthening the power of labor unions. It is far more difficult to justify the admiration for Holmes that persists today among many modern liberals, and some conservatives.
UPDATE: Although I don't have the space and time to document it in detail, I think that Holmes' reputation for cogent legal reasoning is also overblown. Setting aside the often flawed conclusions of his opinions, he also routinely failed to address important arguments on the other side. Many of his most famous opinions, including the much-praised Lochner dissent (which simply ignored the evidence suggesting that the Fourteenth Amendment was intended to protect economic liberties, and gave short shrift to relevant precedents going against him) suffer from this weakness. Holmes' opinions often seem better-reasoned than they really are because his great rhetorical skill masked their substantive weaknesses.
UPDATE #2: The original version of this post incorrectly stated that Holmes dissented in the important civil rights case of Buchanan v. Warley (a result of faulty memory on my part). I have now corrected the mistake.