The straight-line algorithm certainly creates plausible and impressive-looking results for such a simple rule.

Another idea, that might wind up in practice being a little like multi-member districts: don't define district boundaries, but rather 'home points' for each seat. Let any voter vote in their choice of one of the N closest-homed seats. This needs more modelling, but my hunch is even if you let partisans place the points as aggressively as possible, simple planar geometry would prevent them from contriving many safe seats from arbitrary placement. (Also, the placing of 'home points' might be very amenable to an automated process.)

Fair pie-cutting algorithms might also help; perhaps something like: If N districts are needed, the dominant party gets free rein to create 3*N equal districts; then the minority party chooses which groupings of 3 become the real districts. Again, more modelling necessary but shenanigans in creating unbalanced phase 1 mini-districts might tend to strengthen the hand of the minority party in phase 2.