Old school, brute force detective work. Searched on "vintage fantasy poster" and flipped over the image results. Then just started scrolling down until I saw *something*. I scrolled down 2-3 screens worth and stopped on this:
Not sure why, but it just
felt like it would be the style of the mystery poster from the description. When I clicked on it, Google showed me a few more similar images and bingo bango I noticed the two distinct blobs in the blurry video screen cap -- one for the rubble, one for the dude man.
The whole thing took about 35 seconds from the time I started typing "vintage fantasy poster" into Google. And by the way, the other poster I stopped on was done by the same artist.