I would recommend that you try Craigslist.
Also, here's the combined Classifieds of newspapers which serve Lynnwood and Everett:
North Sound Classifieds
There are other online resources such as Rent.com, Forrent.com, and Apartments.com
You might find more houses to rent, compared with number of apartment buildings, in that area. A house might be something to consider where landlords might be more likely to rent to you and Doggie. Since a Shiba is smaller than, say, an Akita or Husky, in terms of
size an apartment might be all right but apartment landlords often have blind spots in their minds about dogs, regardless of size. So a small house is worth considering, no?
Good luck to you both!