They suggest the rainbow color map is a poor choice because it hides small details. I'm advocating regularization which ensures that you have no small details.
But after reading that paper, I do agree that rainbow has some significant issues. One thing that might be worth trying: make a rainbow color map, but map values to colors in such a way that |x-y|=C x cielab_dist(color(x), color(y)).
I believe the 'Spectral' colormap (with a capital S) in matplotlib does exactly that.
Based on the names, it seems [1, 2] (along with all the other capitalized matplotlib colormaps) to be a ColorBrewer [3] colormap, which are all designed with these perceptual considerations in mind [4].
But after reading that paper, I do agree that rainbow has some significant issues. One thing that might be worth trying: make a rainbow color map, but map values to colors in such a way that |x-y|=C x cielab_dist(color(x), color(y)).