Playing around a bit more with 3D, got a basic Z-Buffer and vertex colors (without perspective correction yet... affine z-buffer?).
This already lets me draw some quite complex scenes without having triangles popping up left and right, and it seems it might actually be faster than naively sorting the polygons.
Scene in question: https://poly.pizza/m/2twvfQfSlHB