Our uppercase letters would certainly be legible to an ancient Roman. These letter forms follow Roman capitals very closely – so closely, in fact, that the letter forms for the font Trajan are taken directly from the inscription on Trajan's column! This script is usually called Roman Square Capitals (it's also called lots of other things because scholars of handwriting can't make up their minds - all of these terms for scripts were made up centuries later) and it's the script used for stone inscriptions. Sure, we use a variety of fonts, but I don't think that would cause much difficulty, since the Romans also saw their letter forms with slightly different variations. We refer to the curvier, more calligraphy-like Roman capital letters as Rustic Capitals, the version used in ancient scrolls and books, and in smaller text on inscriptions that had headings in Roman Square Capitals.

For the lowercase letters, there isn't such a close equivalent. The other main script that we know was used in Cicero's time was called Old Roman Cursive; it was used on papyri and wax tablets and some other mediums that weren't as monumental as a stone inscription. Some of its letters look more like modern lowercase than the capital letters do, like m, h, p, q (though it's slanted), d, and h. Roman Cursive isn't legible to a modern reader without training, though only part of that is due to the letter forms themselves, and over time it came to look a little more familiar: by the 3rd century it has transitioned into New Roman Cursive, which adds a few more familiar letter forms: n, r, u. (Letters like s t l i g and c still look quite different.)

The beginnings of a lot of lowercase letter forms can be seen in the Uncial and Half-Uncial scripts, which date to ancient Roman times but not as early as Cicero. Figuring out the era in which an ancient script developed can be hard for scripts used largely in scrolls and books, because we don't have very many surviving examples. Uncial and Half-Uncial were definitely around by the 4th century CE and may have been around for a couple centuries before that in books that don't survive. Half-uncial in particular looks a lot like modern lowercase but it still has some letters that are very different from it, like g, s, t, and the distinction between i and l.

The Romans didn't use capital letters to emphasize the initials of words or sentences the way we do. The different scripts were just different ways of stylizing the letters. The kind of alternation between scripts that we think of today didn't start developing until the middle ages, and wasn't standard across languages, regions, or styles of manuscript. An early widespread example of distinguishing capital (majuscule) and lowercase (minuscule) text is in a script called Carolingian Minuscule, which evolved from half-uncial letters starting in the 8th century. Charlemagne's administration promoted the use of this script in his empire in contrast to the variety of local scripts that had existed in the previous centuries, so it was written as clearly and legibly as possible. Part of this clarity was that texts written in Carolingian Minuscule typically used capital letters (derived from Roman capitals) to mark the beginnings of sentences.

To judge by the difficulty of reading Roman scripts as a modern person, a Roman couldn't just pick up a modern book and read fluidly. A lot of the letters are similar, though, and our printed material is fairly friendly to the untrained eye, since it has uniform letter forms and word spaces and no lines joining letters together (more like a Roman inscription carved with monumental aesthetics in mind than a Roman personal letter scrawled in cursive). So with a little time they might be able to decipher it by piecing together which missing letters are which.

Edited because I realized I missed part of your question when initially answering this! Also, I am a classicist and not a medievalist, so if any medieval paleographers are here, I welcome additions to the part about post-Roman uses of majuscule and minuscule.

Sources

• The Oxford Handbook of Latin Paleography, ch. 3-5

• Brown's A Guide to Western Historical Scripts from Antiquity to 1600

• The sites I linked in the text