I created a very simple cylinder prefab, that uses the Transparent/Diffuse shader (with no texture). I drop two instances into my scene. I click one instance, and in the Shader editor I change the Main Color to be blue, but that modifies the color of both instance in my scene, whereas I'd like one to be blue and one to be red.
What am I missing?
You need to use two different materials. You can leave one instance of the prefab as it is, but you need to create at least one Material in the Project View, and drag that onto the other instance.
If you want, you can script this using Renderer.material.color, which will create instances of the material. You'll get an "error message" telling you that you shouldn't have done that, if you do this with an Editor script, but I don't think it actually causes problems.