Este é o seu código acelerado, carregando os dados em arrays e fazendo a comparação com eles:
Sub compare_cols122()
Dim NameList As Worksheet
Dim i As Long, j As Long
Set NameList = Excel.Worksheets("Names")
Dim rngNames As Range
Set rngNames = Range("A1", Range("A1").Offset(Rows.Count - 1).End(xlUp))
Dim varNames As Variant
varNames = rngNames.Value2
Dim rngData As Range
Set rngData = Range("C1", Range("C1").Offset(Rows.Count - 1).End(xlUp))
Dim varData As Variant
varData = rngData.Value2
Application.ScreenUpdating = False
For i = LBound(varNames) + 1 To UBound(varNames)
For j = LBound(varData) + 1 To UBound(varData)
If varNames(i, 1) <> "" Then
If InStr(1, varData(j, 1), varNames(i, 1), vbTextCompare) > 0 Then
NameList.Cells(j, 3).Interior.ColorIndex = 6
NameList.Cells(i, 1).Interior.ColorIndex = 6
Exit For
Else
End If
End If
Next j
Next i
Application.ScreenUpdating = True
End Sub
Observe que a troca dos loops internos e externos só retardará a pesquisa, independentemente de quão raros sejam os resultados.