"Bald Faced Lie" vs. "Bold Faced Lie"
Solution 1:
The Facts on File Dictionary of Word and Phrase Origins (1997) has this entry for "barefaced liar":
Barefaced, "beardless, with no hair upon the face" may have been coined by Shakespeare in A Midsummer Night's Dream, where it is first recorded. Within a half a century or so it came to mean bold, audacious, impudent, or shameless, like many boys, who were barefaced. By 1825 we find "the barefacedness of the lie" recorded, and Harriet Beecher Stowe writes of a barefaced lie in Uncle Tom's Cabin [in 1852].
To similar effect is the entry for "bare-faced lie" in Christine Ammer, The American Heritage Dictionary of Idioms (1997):
A shameless falsehood....The adjective barefaced means "beardless," and one theory is that in the 1500s this condition was considered brazen in all but the youngest males. By the late 1600s barefaced also meant "brazen" or "bold," the meaning alluded to in this phrase.
But "barefaced lie" goes back much farther than 1825. Here is an excerpt from The History of King-killers: Or, the 30th of January Commemorated (1719):
Prynne with his usual Impudence, and without any Regard to Truth, in his Book entitl'd Canterbury's Doom, &c, falsly writes, that Burton was brought into the Star-Chamber, and there censur'd for the aforesaid Sermon and nothing else. Such a barefac'd Lie at a Time when that Affair was so fresh, would have deterr'd any Man that made the least Pretence to Modesty from publishing of it ; but Prynne was of the Mind of the late no less famous Ferguson, who being about to publish in Print a most notorious Falshood,was told by a great Man, whom it most concern'd to have the same believ'd, that it was inpossible to impose such a Piece of Forgery upon any Men of Sense, Do you publish it, reply'd Ferguson, and tho' never so absurd, Fools will believe, and the Wier seem to believe it.
And here are the opening lines of a "On Hearing of His Royal Highness's Visit to Mr. Pope at Twickenham," in The Gentleman's Magazine (October 1735):
Yield, envoy yield; nor longer vainly try/The tim'rous whisper, or the barefac'd lie;/Greatness, superior to thy arts, can view/Its kindred virtues, and admire 'em too.
Other early appearances of the phrase appear in Edward Lewis, "Oxford Honesty: or, A Case of Conscience,"strong text third edition (1751); in William Romaine, Twelve Discourses upon Some Practical Parts of Solomon's Song, second edition (1759); and in John Trusler, Life, or the Adventures of William Ramble (1793). Numerous instances appear from 1796 forward.
The earliest association of "bold-faced" and "lie" that I've been able to find in a search of Google Books is this item from Richard Baxter, "The Catechising of Families" (1682/1707):
He that by Equivocation useth unapt and unsuitable Expressions, to deceive him that will misunderstand them, is to be blam'd: But he that will stand openly Bold-faced in a Lye, much more.
However, boldfacedas a pejprtive adjecyived goes back to the very early seventeenth century. From a 1604 translation of Jean Chassanion, Traité de la marchandise des prestres. The Merchandises of Popish Priests](https://books.google.com/books?id=h6mA0ovYjbUC&pg=PP40&dq=%22boldfaced%22&hl=en&newbks=1&newbks_redir=0&sa=X&ved=2ahUKEwi--af-95HsAhWYqZ4KHRz_C-gQ6AEwAHoECAAQAg#v=onepage&q=%22boldfaced%22&f=false):
Oh wickednes, oh bold faced impudence, able to ouerreach and beguile very wise iudgements.
Farmer & Henley, Slang and Its Analogues (1890) reports that "bald-faced" meant "having white on the face," and led to two contemporaneous slang terms: "bald-faced shirt," meaning (in cowboy lingo) a white shirt; and "bald-faced stag," meaning a bald-headed man.
One of the earliest metaphorical uses of "bald-faced" is in conjunction not with lying but with impudence. Thus, from Register of Debates in Congress (April 28, 1836), we have this fragment from a speech by a Mr. Moore of New York:
And yet, in the teeth of all these facts, in contradiction to all experience, and in defiance of the concurrent testimony of history, our modern aristocracy have the presumption, nay, the bald-faced impudence, to allege that the people have ever a propension to sedition and plunder.
Similar instances of "bald-faced impudence" occur in Punch, volume 17 (1849) and in The Medical Age (January 25, 1895).
Gilbert A. A'Beckett, The Comic History of England (1847) brings "bald-faced" (in the strict sense of "white-faced") and "bare-faced" into close proximity, in this sentence:
The extraordinary hilarity of the bounding hart attracted the attention of Rufus, who drew his bow, but the string broke, and Rufus not having two strings to his bow, called out to Tyrrel to shoot at the bald-faced brute for his bare-faced impudence.
Wentworth & Flexner, Dictionary of American Slang (1960) has entries that cite "barefaced lie" and "bald-faced lie"—but not "bold-faced lie"—as current slang.
My guess is that all three expressions are tangled up historically in various forms of bare-, bald-, and bold-faced behavior, all entailing the same general notion of audacity, impudence, and shamelessness. Under the circumstances, it's hardly surprising that variants of all three words are linked to the words lie and liar.
Another Meaning of "Bald-Face"
Maximillian Schele De Vere, Americanisms: The English of the New World (1872) offers this entry in a chapter on "Cant and Slang":
Bald-face, one of the many slang terms under which bad whiskey passes in the West.
Likewise, John Russell Bartlett, Dictionary of Americanisms, Second Edition (1859):
BALD FACE. Common (penny) whiskey, particularly when it is new; also figuratively and appropriately called Red Eye.
A "bald-face lie" might thus be a lie that someone tells under the influence of bad whiskey; it is far more likely, however, that the drink-related term is unrelated to lying and refers simply to the immediate effect of the liquor on the face of the imbiber.
Update (September 30, 2020): Earlier instances of 'barefaced lie'
A search of the Early English Books Online database—which covers the period from 1475 to 1700—turns up several matches for "barefaced [or barefac'd] lie [or lye]." The earliest of these is from Daniel Whitby, Aonoz Tez Kisteōz, or, An Endeavour to Evince the Certainty of Christian Faith in Generall and of the Resurrection of Christ in Particular (1671), where the expression appears in two distinct places:
I say impossible it is, that men declaring that these things were acted and experimented, in the places where those persons lived who embraced this Doctrine, and for whom those Gospels were indited which contained, these things, should by such Gross untruths prevaile upon these persons, to embrace that story, which told these Barefaced lyes, for a divine unerring History, fit to be sealed with their Blood. ...
...
Prolegomena, in order to the demonstration of the Resurrection of our Lord. 1. That the Apostles did presently attest the thing. 2. That this attestation could not be a barefaced and notorious lye. ...
From "A Clear Discovery of the Malicious Falsehoods Contained in a Paper Printed at London, Intituled, A True Relation of What Is Discovered Concerning the Murther of the Archbp of St. Andrews'" (1679):
It shall be unnecessary to say any more of the other manifest and barefaced lies contained in the foresaid Paper, such as that the murderers hurt none of his servants, except the Postilion; whereas the best armed of his servants was wounded in the head by a sword, and his Daughter, besides the wound of her Thumb, had another in her Thigh; and that they dragged him out of his Coach, whereas indeed he very composedly opened the door of the Coach himself, and with meekness and resolution stept out, and went forward to the murderers, who were, with so Grave and Reverend a Presence and Resolution, so much stunn'd and amazed, that they looked upon one another, and stood a little while like men confounded, and unresolved what to do: ...
From John Dryden, The Vindication, or, The Parallel of the French Holy-League and the English League and Covenant Turn'd into a Seditious Libell Against the King and His Royal Highness by Thomas Hunt and the Authors of the Reflections upon the Pretended Parallel in the Play called 'The Duke of Guise' (1683):
Fat Falstaffe was never set harder by the Prince for a Reason, when he answer'd, that that if Reasons grew as thick as Black-berries, he wou'd not give one. Well, after long pumping, lest the lie shou'd appear quite barefac'd, they have found, I said, that at King Henry's Birth, there shone a Regal Star: so there did at King Charles the seconds: therefore I have made a Parallel betwixt Henry the third, and Charles the second. A very concluding Sillogism, if I shou'd answer it no farther.
And from John Turner, "A Second Representation of the Hospitaller of St. Thomas Southwark's Case in an Humble Address to the Right Honourable Sir Thomas Pilkinton, Lord Mayor of the City of London" (1689):
I never heard any thing urged to palliate so gross and palpable a falshood, but that the consideration was not given him by the same Persons that ejected him from hence, and therefore they conclude and argue like themselves, who understand neither Premisses nor Conclusions as they ought to do, that one was not given him in lieu of the other: but those Gentlemen know best upon what motive they did it, and to them I make my humble, but yet confident Appeal, which Mr. Hughes with all his impudence dare not do, and I do really resent the injury, and affront which is done to the City and the Court of Aldermen by such a barefac'd Lye, insinuated with all the seeming sincerity and address, which is only natural to truth, and very ill becomes that Falshood and disguise, which incapable of a modest and just asseveration, needs a meretricious and feigned one to support it.
EEBO searches for 'boldfaced lie' (in various forms) turned up no matches.
Solution 2:
A bald-faced lie is one that is:-
easy to see and understand as being bad
showing no guilt or shame : not hiding bad behavior
The same source lists bold-faced as
displaying or marked by rude boldness: the child proceeded to tell a bold-faced lie despite the evidence right in front of us
There is also a bare-faced lie:-
a : open, unconcealed: barefaced impudence
b : having or showing a lack of scruples: a barefaced lie
I'm inclined to the view that bold-faced is a mishearing of bald-faced, which is the usual American English version, and bare-faced is the usual British English version; both of these mean
1 : having the face uncovered: a : having no whiskers : beardless b : wearing no mask
Solution 3:
I’ve only know it as barefaced lie. Barefaced means ‘impudent’ or ‘shameless’. The OED has a supporting citation from 1852.
This nGram shows that barefaced lie has been more frequent than the two alternatives over a period of 200 years.