Did the Vikings run into native people on Iceland or Greenland?

Since I've recently answered one that engages with medieval and early modern interaction with the Thule people in Greenland, in this answer I'm going to focus on Iceland!

The traditional date of settlement for Iceland is 874, by Ingolfur Arnarson, who landed in settled in the area around Reykjavik. The Settlement Exhibition, in Reykjavik, gives us a pretty close approximation to that - it is the foundations of a hall dated to 871 plus or minus 2 years. This traditional narrative comes to us from the early 12th century, in the Islendingabok of Ari Þorgilsson. However, according to Ari, Ingolfur was not the first human to settle in Iceland! To quote him in translation:

At that time Iceland was covered with woods between the mountains and the seashore. There were then Christians here, whom the Northmen call papar, but they later went away, because they did not wish to stay here with heathens; and they left behind them Irish books and bells and staffs. From this it could be seen that they were Irishmen.

(translation by Sian Grønlie)

According to Ari, therefore, the "native" inhabitants of Iceland were actually Irish! And this makes some sense - Irish ascetic hermits settled all across the Hebrides, the Orkneys, and the Shetlands, all places with substantial Norse contact and settlement in the Viking Age. This, then, groups Iceland with these other settlement patterns, conveniently "priming" the land for the conversion to Christianity in the year 1000. This ideological priming, and a lack of artifacts of the type Ari describes, throws doubt on his narrative, sadly, and the fact that they peacefully vanished shortly after the Norse arrived is suspicious at best.

But, Ari's narrative is not the only evidence we have for Irish settlement! All around Iceland are some place names with either the element "Ír" or the element "pap." Some examples exist in Breiðafjörður, in the northwest of the country, and in the Eastfjords, like the island of Papey. These names may suggest at least popular belief in the existence of the papar, even if its scant evidence for actual interactions between them and Norse settlers. However, it must be said that alternative explanations have been proposed that assign a much later date to some of these names, and so that's not necessarily persuasive. (e.g. Helgi Þorláksson 2012, "Frá Byrstofu til Breiðafjarðar. Voru írskir kaupmenn við Breiðafjörð undir lok miðalda?" [From Byrstofa to Breiðafjörður. Were Irish merchants in Breiðafjörður at the end of the Middle Ages?])

The other piece of evidence is archaeological. Kristjan Ahronson has an ongoing project mapping a cave in southern Iceland, privately owned near Seljalandsfoss. This small cave was carved out of a boulder by human hands, and is covered in thousands of carved crosses. Ahronson argues that the design of these crosses is consistent with a style found in the Hebrides around 800 CE, and that we should therefore attribute this cave to an Irish hermit at around that same time period. This argument is fascinating (I've gotten to see and go into that cave), but controversial. You can read more about it in his book Into the Ocean.

Now, there's a big difference between 800 and 874, and the presence of one hermit in 800 doesn't mean the island was inhabited in 874. However, there is also currently an excavation in Stöðvarfjörður that the head of the dig, Bjarni Einarsson, claims also dates to around 800! This is a large longhouse with a huge metal hoard attached to it, which is unbelievably significant. It's much to early to say whether that dating is correct and what exactly the implications of that is, but it is appealing - if both of these projects get supplemental evidence, then that would put Irish hermits and Norse sailors in Iceland at the same time. That still does not prove any interactions, but it invites further research. The field is still changing all the time, and this is a research topic that is still very much in flux.