For evergreens, try a Golden Globe arborvite. They stay pretty small (2-3'), keep a nice rounded shape w/no pruning, do well in LOTS of shade (mine's in almost 100% shade), and has a wonderful yellowy color in the spring/summer/fall and a kinda blah color in the winter.
http://davesgarden.com/guides/...
You can also also try Red Barberry. Problem with them is the thorns are nasty. :(
http://davesgarden.com/guides/...
I wanted to grow some Evergreen Huckleberry, but they wouldn't survive here (too cold).
http://www.burntridgenursery.c...
That Burnt Ridge Nursery has plants native to the NW, so they'd be a great resource.