Here's a version that follows your connectivity, maintains the 0.5% deviation, only splits the three big counties, and generally addresses the negatives.
Tacoma is now in a Pierce-only district so only the remainder of Pierce only makes up 20% of the Olympia district. The Everett district is 63% Snohomish and 37% Kitsap. The remainder of Snohomish is only 37% of the Bellingham district. So, King dominates 3 districts, and Pierce and Snohomish each dominates one district.
I like this map, because it maintains the connections and makes sense. The part of King County in the green district is mostly Enumclaw which goes well with the district. Eastern cities are kept together such as Wenatchee-E. Wenatchee and the Tri-Cities. Probably one of the best maps so far, and Island county should stay in the yellow.