A couple of links to check out for local advice:
https://www.dnr.wa.gov/urbanfo...
https://extension.wsu.edu/loca...
https://my.spokanecity.org/urb...
I would contact the state forestry people to see if they might have a program for selling or giving away trees to state residents. Even if they don't offer free or cheap saplings, they may be a good source for recommendations. Likewise your county extension agent.
I see that you aren't far from Spokane, and here's a pdf link to a list of recommended street trees for city residents:
https://static.spokanecity.org...
I think a
Vine Maple (Acer circinatum) or
Douglas’ Maple (Acer glabrum var. douglasii) might be a good, non-toxic-to-dogs choice. I think both are pretty variable in form, but from what I'm reading, Vine Maple (Acer circinatum) is not vine-like when grown in full sun. Douglas Maple can be a multi-stemmed shrub 6-12' tall or a tree up to 30' tall. I'm not sure if the difference is simply due to pruning, or if there are clones or varieties that are more tree-like and others that are shrubby. A tree nursery or someone at one of the above links can probably provide expert advice.
If it's not inconvenient, a trip to the Finch Arboretum in Spokane might be helpful?
Good luck!
