Increasing it up to the state level maybe any smaller and you'll still have room for gerrymandering. Could even have districts still for people to have a person to directly go to but who represents which district is down to the statewide percentages. I'd love to see something like that combined with a ranked choice system. First past the post really heavily incentivizes a 2 party system.
Then make the districts bigger to compensate for this effect.