if you get a rental car in Seattle, its just a thirty minute drive north on the 5 then east for three miles on (i think) state route 2 to get to Harvey field. you'd better www.mapquest.com it from Sea-tac to be sure. But its a nice little airport and they rent a champ that is in good condition. Also, Boeing field is right next to sea-tac (well just north about five miles) and they have like four or five FBO's I don't go there very often though so you might want to check the AOPA website to find out if those FBOs have taildraggers. hope that helps...
ProAire at Arlington Airport (KAWO -- 40 minutes north of Seattle) has a Cessna 170 for rent. Nice people.
I think Island Air (mentioned above) sometimes flys their cubs out of Boeing Field. I seem to recall a "Learn to Fly" sign next to one of the cubs in the Northeast corner of the airport. Wings Aloft at Boeing Field may still have a Citabria, but they're a club so they may not rent to non-members.
Finally, there's a Citabria available up here on Orcas Island for dual instruction only. IM me if you want details.
Interesting timing. I was just up at PAE this morning, home on vacation, and I came across a flight school called Northwest School of Aviation that rents a nice J3 for $65 dry. It's down for annual at the moment, should be up soon, but it's a sharp looking Cub. Don't have a number or cantact info on me at the moment...I'll post it when I find it.