How can I detect edges between different colours of the same brightness? I'm looking for an algorithm that can identify edges across which colour is changing sharply, rather than just finding changes in brightness.

Is this just a matter of using a different colour space with existing edge detection algorithms, or is there a better approach?
I think you can convert from the RGB space to the HSV one, or whatever color space has the HUE in a single channel.

Take the HUE channel, and make the edge detection on that one.

Here a simple Matlab script to achieve the result.

I = imread('image.png');
hsv = rgb2hsv(I);
hue = hsv(:,:,1);
edges = edge(uint8(hue),'sobel');
imshow(edges);