Colin,
Thank you very much for your response, I've finally had some time to get back to this. the challenge I have is that I don't always know what kind of node is going to be connected to the Base Color output node of the substance. In the example I posted it's a "baseMaterial", but I'm doing this as a batch process on a bunch of substances, and I have no guarantees of the type of the node connected. It could looks like this:

But it could also look something like this:

and I need to be able to programmatically inject some nodes in between those two.
The answer you gave me at least pointed me in a direction to try out a few other things, so I'm posting the solution I came up with for anyone who might run into a similar problem:
"rightNode" is the node who's input I need to modify, in the pictures above it's the "Base Color" output node of the substance:
# First get the left node
leftNode =aGraph.getNode(rightNode.getConnectedNodesUID()[0])
# Get an ordered list of all the UIDs for the output pins of the leftNode
listOfOutputIDs = []
for eachPin in leftNode.mCompOutputs :
listOfOutputIDs.append(eachPin.mUID)
# Get the UID of the connection to the right node
UIDConnectedToRightNode = rightNode.getConnections()[0].mConnRefOutput
# Get index of the matching UID on the leftNode from the ordered list we built
indexOfLeftOutputPin = listOfOutputIDs.index(UIDConnectedToRightNode )
# Get the identifier for the output pin of the leftnode so we can connect to it
leftPinIdentifier = leftNode.getDefinition().getAllOutputs()[indexOfLeftOutputPin ].mIdentifier
# Actually do the connections to inject newNode in between leftNode and rightNode
aGraph.connectNodes(aLeftNode = leftNode, aRightNode = newNode, aLeftNodeOutput = leftPinIdentifier)
aGraph.connectNodes(aLeftNode = newNode, aRightNode = rightNode)
This works for me now, but currently it assumes the rightNode only has one input connection. If the rightNode had multiple input connections, this could get a lot more annoying. If there's a cleaner way to achieve the same result I'd love to hear about it. Thanks!