How can I effectively import and texture a large height mapped terrain mesh?
I have since found a good solution for my problem. What I've done is break up the mesh into individual "chunks" and then applied a material to each to texture it. I discovered that Blender can handle that many objects and my perception otherwise was due to the script functions I was using. Here is some pseudo code for what worked for me with good performance (10-15 seconds to create 8112 5x5 objects with 25 faces each):

for chunk in chunks:
    mesh = bpy.data.meshes.new(str(chunk.name))
    mesh.from_pydata(chunk.vertices, chunk.edges, chunk.faces)

    obj = bpy.data.objects.new(obj+str(chunk.name), mesh)
    obj.location = (chunk.offset.x, chunk.offset.y, 0

    bpy.context.scene.objects.link(obj)


The key was to not use any operations in bpy.ops but to instead create and link the mesh/obj/scene for better performance. See here to understand details Python performance with Blender operators.