Set the color of faces in python efficiently
This seems almost instantaneous and much faster than the original function above:

import bpy, time
from random import randint

start = time.time()

def paint( obj1, obj2, mat1, mat2, pairs ):
    # First assign the 2nd material as the active, default material for all faces
    obj1.active_material = mat2
    obj2.active_material = mat2

    # Add mat1 to both objects as the 2nd material slot (index=1) if not already included
    if mat1.name not in obj1.data.materials:
        obj1.data.materials.append( mat1 )
    if mat1.name not in obj2.data.materials:
        obj2.data.materials.append( mat1 )

    # Now iterate over the pairs and set material 1 as the active material for the selected faces
    for p in pairs:
        i1, i2 = p
        obj1.data.polygons[i1].material_index = 1
        obj2.data.polygons[i2].material_index = 1

    obj1polygons = [ p[0] for p in pairs ]
    obj2polygons = [ p[1] for p in pairs ]

    # Set mat1 as the material for all polygon indices not in the pairs list
    for i in range( len( obj1.data.polygons ) ):
        if i not in obj1polygons:
            obj1.data.polygons[i].material_index = 0

    for i in range( len( obj2.data.polygons ) ):
        if i not in obj2polygons:
            obj2.data.polygons[i].material_index = 0

faceCount = 512
redFaces  = 50

pairs = [ ( randint(0, faceCount - 1 ), randint(0, faceCount - 1 ) ) for i in range( redFaces ) ]

mat1 = bpy.data.materials['mat_one']
mat2 = bpy.data.materials['mat_two']
obj1 = bpy.data.objects['obj1']
obj2 = bpy.data.objects['obj2']

paint( obj1, obj2, mat1, mat2, pairs )
print( "Ran for: ", round( time.time() - start, 5 ) )