B'ham rox if you ask me. I lived there for 5 years and still go up often. The YMCA actually has a decent plactic gym, for a YMCA in bellingham. It's no vertical world in terms of size, but they just expanded. For the cost of a membership at a rock gym you get the whole YMCA membership.
There's always fun stuff to do. The beaver inn has deep fried pickles. The cost of living is cheaper than redmond. As for outdoor climbing, there is bouldering at larabee and a cool slab to boulder on at this little cove on the water right before there, not sure what that's called. Oyster dome has a few climbs on it, though I've never climbed the wall I've sat atop watching after riding up the trail from the I-5 side (blanchard hill trail). You will be close to darrington as well as squirmish (about 2hours methinks).
And dont get me started on the mountain biking.
I would probably move there if I could get a decent job.