You could also consider the wilderness coast of the Olympic Peninsula, although of course you'd fly into Seattle for that one. Look up Olympic National Park on the nps.gov site--they have excellent trail descriptions. For more detail call ONP's Wilderness Information Center in Port Angeles, WA--they'll be happy to help you plan a trip. Be sure to check the tide tables, though, for the period you're going, as you can get around many points only at low tide. If high tide is mid-day, you'll be doing a lot of waiting!
Unless the present drought continues the rest of the winter, you'll need to stay below 3,000 feet elevation in April. In past years, the snow level has often been lower!
Another caveat in the Columbia River Gorge: leave absolutely nothing, of value or otherwise, in your car!