For early season hikes in Washington, there are really two strategies: go low or go east. The eastern slopes of the cascades typically melt out a couple of weeks earlier than the western slopes. All other things being equal (and with a couple of notable exceptions) most of the high country on the east side of the Cascades is quite accessible by early July. This year might be a little different, but if May and early June are mild I would expect things to be pretty clear.
My favorite trips on the high east side is either the Summer Blossom/Chelan Summit trip to Stehekin (3 to 7 days and you need a car shuttle and a car that can handle a wicked bad road) or the High Pasayten section of the Boundary Trail (from around Spanish Camp to Horseshoe Basin) — once again it helps to have a friend for the car shuttle and a nice bad-road vehicle.
Going low can work too. Any of the big river valleys provide nice early-season walks. As well as the aforementioned Suiattle River (the trip to The Great Fill is awesome if you can make it — the upper miles of the trail are just gone now) you can go to Big and Little Beaver Creek (although probably a boat ride on Ross Lake is required to make the trip feasible in a 3 1/2 day weekend) or East Bank Trail on the opposite shore of Ross Lake — best when the lake is full pool which usually happens around the third week of June.