This! Interpolating in linear RGB space is the biggest issue, I'm sure it will improve a lot simply by using a more suitable colorspace. Triangles might not be noticable at all then, except in extreme cases (which are undesirable anyways).
A-B
|/|
C-D
But I'll try another color space first, it should be easier to implement.