Sorry, I forgot to address this in my original post. The thing about Seattle is, we don’t have a lot of history, at least in terms of cuisine. We have a few joints that have been open for decades, but most of them are dives and can’t really be recommended (e.g. the Five Spot). More frequently, stuff gets torn down, renovated, resold, reworked, and recycled. The restaurant at the top of the Space Needle, for example, has been there for 41 years, which is ancient in Seattle time.
The best previous example was the Dog House, a hilarious throwback 24-hour diner on the edge of downtown. The waitresses were surly, the food was indifferent, the decor was 40s-turning-into-50s classic vinyl booth. This is the place that makes frequent appearances in J.A. Jance’s J.P. Beaumont mysteries, by the way. It had been around forever, and was an institution, until suddenly, back in '91 or '92, they announced they were done. Business was brisk those last few weeks; I was there less than 24 hours before they closed, and I remember ordering off a xeroxed menu because all the originals had been stolen as souvenirs. A couple of the local TV stations even did live feeds to cover the closing. It reopened shortly thereafter under new ownership and a new name, but it wasn’t the same.
The thing about Seattle is, we don’t really have a tradition in terms of culture. Yeah, we’ve built airplanes for many decades, but even that is going away, and in any case that doesn’t really tell you what to expect from the restaurants. The more recent software boom means we’ve got people with money who are more interested in the latest thing than in any kind of consistency, which has meant a lot of restaurant turnover; twenty years ago, nobody had heard of Thai food, but now there’s one on every other block.
More frequently, restaurants come and go based on economic whim. Of course, that’s true anywhere, but it’s even more unstable here; you can’t count on the institutions. In addition to the Dog House mentioned above, there was a dive bar on Broadway called Ernie’s. This is a place where the regulars had their own bar stools, and they didn’t have to say a word to have their preferred drinks put in front of them. I once saw a bartender look at a guy on his stool, then come out from behind the bar and catch the guy as he started to slip backward. The timing was exquisite; the bartender was coming out before it was apparent the guy was passing out, and a well-placed hand between his shoulder blades put him back up against the bar. It was almost graceful, except that it was kind of sad, too. Anyway, the bar faded away as the neighborhood got gentrified; first it turned into an upscale bar called “Ilene’s, with Ernie Room,” and now it’s a breakfast joint, one of three “Julia’s” in the city (the other two are in Wallingford and Ballard, IIRC).
In fact, as I rack my brain, I can think of only two restaurants that have been around long enough to really reflect Seattle history: Ivar’s, which most people think of for its numerous fast-food fish-n-chips outlets but that has a pretty good “true” restaurant called (IIRC) the Captain’s Table near Gasworks Park, and the Lock Spot, which has been in Ballard absolutely forever (it’s right next to the Locks park, a must-see destination) and has decent but not great food. These are places that are about Seattle’s maritime tradition, and are worth visiting if you’re looking more for an experience of the city’s history, i.e. who we were when the city was being founded, and less for outstanding cuisine.
Aside from that, for history, you should hit the Pike Place Market. The Athenian is probably the truest historical restaurant; beyond that, mostly it’s a bunch of quick-snack booths with generic food (teriyaki-from-a-bottle, for example), not to mention high turnover (though the donut fryer has been there a while). Still, in a very general sense, the Market has been remarkably stable for decades; it’s still a functional shopping area for local merchants and residents, and has resisted out-and-out touristification like, say, Fisherman’s Wharf in San Francisco. And maybe that’s the best sense of history you can find: Rather than a specific single restaurant with its own lengthy provenance, you would enjoy an overall environment where an unending series of scrappy entrepreneurs over the years have wedged themselves temporarily into a tiny hole to make a start to their careers, before moving on and making the space available to the next person trying to make a go of it.