How well-known were the stories of Julius Caesar, Marc Antony, Cleopatra, etc. before Shakespeare and how large of a role did he play in popularizing them?

Well that really depends on who and when you mean, the Late Roman Empire is a different case than Medieval France, and then we have to factor in that socioeconomic factors played a role in a person's understanding of history.

That said, I am assuming you mean Elizabethan England and it might interest you then to note that there had actually been a number of plays dramatising the lives of historical figures like Caesar, Cleopatra, Herod and the like along with Biblical and mythological figures Kit Marlowe's play The Tragedy of Dido Queen of Carthage is based directly on Virgil's Aeneid for instance. The influential author Geoffrey Chaucer's The Legend of Good Women features none other than Cleopatra as its first subject.

After the deeth of Tholomee the king, That al Egipte hadde in his governing, Regned his quene Cleopataras; Til on a tyme befel ther swiche a cas, That out of Rome was sent a senatour, For to conqueren regnes and honour Unto the toun of Rome, as was usaunce, To have the world unto her obeisaunce; And, sooth to seye, Antonius was his name. So fil hit, as Fortune him oghte a shame Whan he was fallen in prosperitee,

Chaucer was himself inspired by the 14th Century author Boccacio's De Mulieribus Claris (The Illustrious Women) which features biographies of 106 women from Medieval and Classical history like Agrippina, Cleopatra, Julia, and Zenobia, as well as mythological women and goddesses like Dido, Juno, Isis and Minerva. Another user brought up her appearance in Dante's Divine Comedy, but a number of plays, poetry and artwork from the 15th Century onwards feature figures like Julius Caesar, Marc Antony and Cleopatra prominently as part of a general revived interest in Classical literature.

Roman history plays were en vogue to a certain extent, and their prevalence would seem to indicate that Shakespeare's work was not particularly groundbreaking in its subject matter. Shakespeare's work enjoyed more popularity than most previous examples and his presentation of these stories in a more popular style would explain the amount of plays and operas imitating its style and subject matter such as John Dryden's All For Love; or The World Well Lost which was one of many imitations but this one did not fade into obscurity like the vast preponderance of its contemporaries. Dryden openly admits this in his preface

The death of Antony and Cleopatra is a subject which has been treated by the greatest wits of our nation, after Shakespeare; and by all so variously, that their example has given me the confidence to try myself in this bow of Ulysses amongst the crowd of suitors, and, withal, to take my own measures, in aiming at the mark.

Shakespeare can certainly be argued to have popularised and further developed history plays as a whole, although this also encompasses those plays concerning the lives of Henry V, Macbeth and King Lear. His plays, while not the first of their kind by any means, influenced the works that came after it to a profound extent that is still palpable today. So while he did not introduce these subjects and characters into the popular imagination, he did define them by their characterisation and iconic place in Shakespearean literature.

I would be interested in what any Medievalist that might be in the house could say about what the average person's grasp of Classical history might have been in urban Medieval England.