When was the first time Rome was mentioned in outside records (and specifically, in Greek ones)?

I don't know, but it is possible that Timaeus c. 300 BC, or Antiochius of Syracuse about a century earlier, was the first Greek writer to mention Rome.

Unfortunately, for some reason I have been unable to link to my various sources.

The first treaty between Roman and Carthage was made in about 509 or 508 BC.

And if it was recorded in historical accounts, the first one written by a non Roman would be the first non Roman mention of that treaty. Although that mention might be based on Roman records of that treaty.

And if the treaty was inscribed on a stone in Roman territory, that would count as a contemporary record of the treaty, though as a Roman record.

Magna Graecia (/ˌmæɡnə ˈɡriːsiə, ˈɡriːʃə/, US: /ˌmæɡnə ˈɡreɪʃə/; Latin meaning "Great Greece", Greek: Μεγάλη Ἑλλάς, Megálē Hellás, Italian: Magna Grecia) was the name given by the Romans to the coastal areas of Southern Italy in the present-day regions of Campania, Apulia, Basilicata, Calabria and Sicily; these regions were extensively populated by Greek settlers.[2] The settlers who began arriving in the 8th century BC brought with them their Hellenic civilization, which was to leave a lasting imprint on Italy, such as in the culture of ancient Rome. They also influenced the native peoples, especially the Sicilian Sicels, who became hellenised after they adopted the Greek culture as their own.

The first Greek city to be absorbed into the Roman Republic was Neapolis in 327 BC.[3] The other Greek cities in Italy followed during the Samnite Wars and the Pyrrhic War; Taras was the last to fall in 272. Sicily was conquered by Rome during the First Punic War. Only Syracuse remained independent until 212, because its king Hiero II was a devoted ally of the Romans. His grandson Hieronymus however made an alliance with Hannibal, which prompted the Romans to besiege the city, which fell in 212, despite the machines of Archimedes.[citation needed]

So it is quite possible that there could be border markers inscribed in Greek and Latin on the borders between Greek city states and Roman territory dating from the fourth and third centuries BC.

Pyrrhus, King of Epirus, fought the Pyrrhic War from 280 to 275 BC in Southern Italy and Sicily. Pyrrhus fought the Romans and was invited to Italy by the Greek city state of Tarantum. The first Greek historian to mention that war would have mentioned Rome.

Dionysius of Halicarnassus (c. 60 BC-after 7 BC) wrote a history of Rome, including the Pyrrhic War, but was writing over 200 years after it happened.

Diodorus Siculus (/ˌdaɪəˈdɔːrəs ˈsɪkjʊləs/; Koinē Greek: Διόδωρος Σικελιώτης Diodoros Sikeliotes) (fl. 1st century BC) or Diodorus of Sicily was an ancient Greek historian. He is known for writing the monumental universal history Bibliotheca historica, much of which survives, between 60 and 30 BC. It is arranged in three parts. The first covers mythic history up to the destruction of Troy, arranged geographically, describing regions around the world from Egypt, India and Arabia to Europe. The second covers the time from the Trojan War to the death of Alexander the Great. The third covers the period to about 60 BC.

So both Dionysius and Diodorus would have relied on earlier writers for their accounts of the Pyrrhic War and other early Greek interactios with Rome, and I don't know which of those earlier writings have survived.

It is possible that the first major Greek historian to Mention Rome was Polybius.

Polybius (/pəˈlɪbiəs/; Greek: Πολύβιος, Polýbios; c.  200 – c.  118 BC)[4] was a Greek historian of the Hellenistic period noted for his work The Histories, which covered the period of 264–146 BC in detail. The work describes the rise of the Roman Republic to the status of dominance in the ancient Mediterranean world. It includes his eyewitness account of the Sack of Carthage and Corinth in 146 BC, and the Roman annexation of mainland Greece after the Achaean War.[5]

Polybius had first hand knowledge of Rome since 167 BC, when he was sent thre as a hostage, although his knowledge of early Roman history would have come from Greek and Roman oral and written sources.

I found this answer to a similar question:

Greek sources: The earliest known reference to Rome by a Greek author is probably by Timaeus, a Greek writer from Sicily who wrote around 300 BC. An alternate hypothetical candidate is Antiochus of Syracuse who lived about a century earlier. Neither of their works survives except in quotations by later writers. For more on the literary sources in Greek, see: Are there any ancient Hellenic references to the Roman Republic, before the Punic Wars?

Phoenicians: The Pyrgi Tablets are not exactly a 'mention' of Rome, but they are sometimes regarded as evidence for a treaty (mentioned by Polybius) between Rome and Carthage conducted around 500 BC. The tablets are in Punic and Etruscan.

Etruscans: The François Tomb from the 4th century BC contains an image of Caelius Vibenna, who figures in the legendary pre-history of Rome, and someone identified as 'Cneve Tarchunies Rumach' or 'Gnaeus Tarquinius of Rome'.

So it seems like Rome didn't begin to be mentioned in surviving non Roman texts, including Greek texts, until about 300 to 250 BC. Which is surprisingly late. Apparently Rome was not mentioned by outsiders in surviving texts until it had already become the ruler of half of the Italian peninsula. And was already a military juggernaut that none of its neighbors could stand up against.