There is a common impression that gerrymandering creates safe districts for the party doing the redistricting. This is not true. Gerrymandering creates safe districts for the party NOT doing the redistricting. This is because the gerrymandering party packs as many of the opposing party's voters into as few districts as possible. I.e. if the gerrymandering party is going to lose, they want to lose by a lot. If they win, they want to win more narrowly in many districts rather than by a lot in a few districts.
Note how the Democrats won in 2006 by running a bunch of moderates for seats that Republicans normally won in places like Ohio and Pennsylvania with Republican gerrymanders. And then lost those same seats in 2010 when their moderates found themselves out of step with their districts.
The greater problem in terms of partisan districts is that voters have been choosing to live in municipalities and neighborhoods with people that are similar to them. So most Democrats live in urban areas where all their neighbors are Democrats. Those produce districts where 90% of the vote is for a Democrat. Republican neighborhoods aren't quite as partisan, the most Republican district (TX-13, R+32) is less partisan than the tenth most Democratic district (FL-24, D+34).
Another way of saying this is that rural and suburban districts are less partisan than urban districts. But they still have a distinct partisan lean. Note that in Cook's partisan measure, the top Republican district is located in the northern part of Texas. There is no way for that district not to be heavily partisan. If there were, they'd have gerrymandered some of its voters into bluer districts in the cities or border counties.
The ten most Democratic districts represent New York City (5 districts), Philadelphia, Oakland, Chicago, San Francisco, and Miami. Like with the Texas district, there is no way to connect these areas in the center of the city with more moderate suburban districts. Note that Miami (Florida) and Philadelphia (Pennsylvania) were redistricted by Republicans who wouldn't if they could. Oakland and San Francisco were redistricted by a supposedly non-partisan commission that nevertheless increased Democratic control of the state (California).
There has clearly been an increase in partisan districts, but blaming it purely on gerrymandering is confusing the issue. The biggest problem is partisan sorting, where people move to areas with like minded neighbors.
By the very nature of incumbency, an incumbent is someone who previously found a winning coalition in that district. In order for an incumbent to lose, there needs to be some kind of change from that.
The change could be that there is an inspiring leader on the top of the ticket. Republicans who lost in 2008 and 2012 blame that. Or the change could be that the inspiring leader is not on the ticket. Democrats in 2010 and 2014 blame that.
Redistricting can change the district. Many Republicans in 2012 and Democrats in 2012 and 2014 blame that for losses. Even in 2016, a court ordered redistricting in Florida toppled several incumbents in what was otherwise a good year for incumbents.
Incumbents also have an advantage with fundraising. After all, it is more efficient to contribute to someone who is currently in office than to someone who might reach office. Contributors can always contribute after the election if they just want to influence policy.
Even in partisan districts, incumbents could lose in primaries. And that happens. However, the advantages of incumbency are even stronger there. Short of redistricting, the incumbent already has a strong group of supporters in that district. Further, while challengers may have their differences with the incumbents, they still prefer the incumbent to the other party's challenger. This often leaves them reluctant to really push on the incumbent's failings.
Voters too have a tendency to punish negative attacks. Yes, they hurt the target, but they often hurt the attacker as well. Those who slightly prefer the challenger may be offended by an attack on an incumbent candidate that they like almost as well.
It's also especially difficult for more moderate candidates to beat more partisan candidates in primaries. The reverse is more likely, as the most active support tends to come from the most partisan. Most primary victories tend to be the more partisan candidate over the more moderate, e.g. Matthew Cartwright defeating Tim Holden after redistricting made it possible for a more partisan candidate to win that district.
Primaries have very low turnout compared to general elections, even in places where the primary is essentially the election for most offices. This gives the advantage to the more committed voters, who are often more partisan as well.
Mine vs. yours
It is entirely possible for me to think that my representative in Congress is great while thinking that everyone else is an idiot. So even though the majority in each district approve of their own representative, we can still think that 434 out of 435 members of the House are stupid.
It also doesn't help that there are multiple groups. There are establishment Republicans and Democrats, liberal Democrats, Blue Dog Democrats, Tea Party Republicans, and other groups. Someone who likes Democrats doesn't like Republicans and vice versa. Someone who likes the Tea Party is frustrated with establishment Republicans who didn't get on board. Someone who likes establishment Republicans is frustrated with Tea Party obstructionism. And let's not get started on how most Democrats regard the Blue Dogs.
Changing my choice for representative doesn't fix that. If my choice loses elections, I'm frustrated. If my choice wins, I'm still frustrated, because my choice fails to deliver. All those other people with their own choices are keeping us from achieving our goals.
Democrats are unhappy with Congress because it's controlled by Republicans. Republicans are unhappy because control of Congress hasn't bought them much without control of the presidency. Perhaps things will change once Republicans control both, come January.