The term you’re looking for is “Fern Bar”. They are characterized by goofy shit on the walls, ferns, and fake tiffany lamps. Wiki states the first one was Henry Africa’s in San Fransisco which started in 1970.
Dark Horse?
While there is an intersection between “fern bars” and “crap on the wall bars,” they are not necessarily the same. There are plenty of fern bars that attempt to be more tasteful, and lots of crap on the wall bars that cater more to the sports bar crowd than the singles market.
As an underage kid in 1964 I walked into Mac’s bar and they had crap on the wall.
I also remember seeing crap on the wall at a local Sunoco station.
Thank you! That’s it! I knew it had “horse” in its name. It immediately became a popular hangout with the college crowd when it opened in 1975. We hadn’t seen anything like it before.
ETA: “Fern bar” is a term I also recall hearing for the first time in the mid or late 1970s in Boulder. Fern bars were decidedly more upscale than a place like the Dark Horse, which was a college dive bar. Fern bars featured cool jazz or a piano player; the Dark Horse had loud rock.
I started eating at a place that did this in the 50s which we regulars lovingly called “Mom’s.” 
Assuming Mac’s was a local joint, I think that’s the whole point of what the chains were trying to establish. Make themselves look like an authentic neighborhood place.
I grew up in a coastal town. Seafarer-themed bars & to a lesser degree restaurants had crap on the walls from my earliest recollections (~the early 60s.) These weren’t chains, just Mom & Pop joints of varying degrees of nautical authenticity. Some joints had real fishermen for customers, others had yachtsmen or wannabe yachtsmen. Or just suburban folks who wanted to eat a fish.
The first I recall of “crap on the wall” restaurants outside of crab pots, manila fishnets, & brass navigation lanterns was the late 60s.
I’m gonna agree with **Southern Yankee **just above that eccentric Mom & Pops had been plastering random locally-available kitsch on their walls since the early 1900s. The regional & soon-to-be national chains ran with that ball as they exploded along with suburbia in the 60s.
Tracer Vic’s in New York was a crap-on-the-wall joint as far back as the 1930s:
Since the date has been pushed to well before my time, I am going to chime in with what I believe to be another possibility. Triple XXX (burgers and root beer). It is certainly a nearly dead chain but it was bigger at an earlier point and I don’t remember their ever not having crap on the walls. So could a “more experienced” doper verify how long they have been putting stuff on their walls?
Ruby Tuesday’s started in 1972 and was one of the early adopters of the look.
Ooops, I mean San Francisco–I remember the NY one. But that pushes “crap-on-the-wall” at *least *back to the 1930s.