Maybe it needs to be a federal issue, not a state issue. Districts have to meet minimum standards or prove why not. Like the law that put voting practices under federal scrutiny.
Minimum standards of area-to-perimeter ratio. Just for one. Federal oversight. Meet the minimum and you can do state's rights to your hearts content. But if you violate the minimum, the federal agency will evaluate and you'll have to have a damn good reason (like a mountain range or a river with no bridges) for violating it.
Or a minimum standard for the percent of legislators of a single party versus the registered voters of that party statewide - cannot deviate by more than 10 percentage points. If 50% of your state registered or voted in one party, then your legislature had better not be 80% of the other party. (That one's harder to make work though)