You can't avoid considering the political concerns here. There's 4 options:
1. Federally mandate independent redistricting in every state at the same time
2. Implement redistricting commissions done as soon as possible in any state with no order
3. Implement redistricting commissions in a specific order
4. Leave everything as it is
The reality is option 2 is not the most fair (option 1 is) when you consider the status quo and that not every state has the opportunity to set up commissions but because no one is going to do option 1, we're going to have to rely on option 2/3 and the courts until it becomes so lopsided that everyone demands option 1. That's probably the only way for the Electoral College to die as well.
And the parties suck, I'd like to pass proportional representation alongside the federal redistricting law to allow multiple parties but that's even less likely than independent commissions in every state.
This country's electoral system is terrible.
I'm a bit puzzled by the part I've bolded. Most studies I have read would argue that moves to a true proportional system tend to strengthen partisanship over individual representation. Italy is sometimes cited as an example where proportional voting leads to voters ignoring the candidates in favor of the label after the name. Is that the direction you prefer?
On the other hand your goal seems to be multiple parties, which can be accomplished with FPTP systems such as in Canada. The need to form majority coalitions in the legislature tends to drive two of the parties to major positions in any system. The question is how to best provide for alternative views.
I've always been torn on the idea of proportional representation, myself. While it would be fairer in that a party that wins ten percent of the vote wins ten percent of the seats, I still like the idea of having "local" representatives representing districts. That's why I prefer mixed-member proportional or a hybrid such as
this (I'd implement it differently, though).