Isn’t it nice when someone does all the work for you?
The Straight Dope looked into the origin of “hard-boiled” as used in crime novels. The phrase began as “hard-boiled egg,” referring to someone who didn’t readily part with money, perhaps because of an older joke that a hard-boiled egg is something that’s “hard to beat.” The phrase may have first appeared in print thanks to Mark Twain. There’s some debate about that, but Twain being an American icon, I like his reference. It continued to mean cheap or petty through 1917 usage.
What I find interesting is the meaning then seemed to change rapidly:
By 1919, hard-boiled meant tough, and often violent. In that year U.S. army lieutenant Frank “Hardboiled” Smith was among several men court-martialed for their brutality in running a stockade outside Paris …
By this point the connection between well-done eggs and no-nonsense personalities was cemented: a 1924 movie comedy about a would-be tough guy was called A Ten-Minute Egg, and author P.G. Wodehouse was fond of describing a particularly forbidding character as a “twenty-minute egg.”