The earliest mention I was able to find was in "THESAURUS GEOGRAPHICUS. A NEW Body of Geography: Or, A Compleat DESCRIPTION OF THE EARTH:" dated 1695.

The passage reads:

"The Figure or Shape of this Country is very Remarkable, and may be well compar'd to that of a Man's Leg, the End whereof seems as it were to kick the Island of Siciliy into the Sea ; the Toes appear toward the Faro, or Watch-Tower of Messina, round Reggio, and the Cape of Spartivento ; the Heel toward Ancona ; the Ham about Ravenna; the Knee toward Piembino, and the Port of Leghorn ; and the Thigh toward the Alps.

Italy is stretched forth toward the South, as it were a Peninsule, in form of a Boot, into the Mediterranean-Sea..."

I believe that Italy was not compared to a boot until boots began to look like Italy. What I mean is footwear in the ancient world like the caligae did not typically have such prominent heels, so this shape would not remind anyone of a boot. Pliny in Natural History (III, Of Italy) instead compares the shape of Italy to an oak leaf:

I may premise by observing that this land very much resembles in shape an oak leaf, being much longer than it is broad…

(There was a fascinating comment that noted that the world's oldest known map is of Italy. The comment disappeared, but this was my question related to it if anyone has any insight on this.)

It's fascinating that the oldest known map is only from 500 BC. I would have thought there would be many examples of much older maps, even if they were only of a small local area (depicting some rivers or major landmarks like mountains perhaps).

Why wouldn't there be numerous examples of much older maps? Why didn't cavemen sometimes sketch maps of their village and nearby important locations? It seems like such a naturally human thing to do, but perhaps not.

You already have very good answers to your precise question, but I'd like to mention that for someone to refer to the Italian peninsula as a boot, you need two things :

1. An accurate enough map that shows the peninsula the way we know it today;
2. A civilization that has boots shaped like that.

You could probably find dates and regions for both premises needed and start looking for boot shaped Italy in documents of that era.

I'm no expert in either, but I know maps weren't really accurate before the 13th or 14th century (when the Portolan chart started to emerge) and it only improved slowly from there until maybe the 16th or 17th century before we had maps close to what we know today (in terms of precision). For the boots, it seems to vary a lot by region and era, as others mentioned already in this thread.