Definitely a feature length movie. Probably in theaters at some point, but might have been a 'made for TV movie'.
It was on TV, in the USA, by early-1999 or earlier (I remember which house I lived in when I saw it on TV, and I moved out of that house before June of 1999, so it must have been then or earlier). My best guess is that I saw it in the 1992-1996 range.
The theme/genre/style of the movie was a fantasy adventure, in the vein of the Schwarzenegger Conan movie, Beastmaster (1982), Red Sonja, etc. (since originally posting this question, I have ruled out those three themselves, see list of movies that have been ruled out, below). The overly-muscled and inadequately armored hero, overly dramatic fight choreography, absurdly fantastical enemies and settings, etc.
The scene I most clearly remember was of the damsel in distress. There were no prison bars or the like. Instead the scene seemed to be in a relatively large open room of a castle or fortress, a great hall or large feasting/dining room or something that size. The walls were definitely supposed to be stone and mortar, very large and rectangular cut stones, this was made clear by the closeups of the damsel in distress, as she was chained to the wall with hands above her head. The lighting of the scene was also somewhat unique, it was definitely firelight, not from candles but from a much larger flame source, such as a dozen or more torches or a large fireplace or fire-pit.
The scene did include both a close-up shot of the damsel in distress' face, as well as a full body shot showing her standing on the ground, and there were no explicit images in the scene. There may have been other scenes in the original cut of the film that were explicit, but none would have been included on the TV run I saw, as it would have been edited for content to the point that anything more risque than a bikini would not have been shown.
Movies that have been eliminated as possibilities:
Sinbad of the Seven Seas (1989)
Barbarian Queen (1985)
Kull the Conqueror (1997)
The Golden Voyage of Sinbad (1973? '74?)
The Beastmaster (1982)
Conan the Barbarian (1982)
Conan the Destroyer (1984)
Red Sonja (1985)
Sinbad and the Eye of the Tiger (1977)
The Sword and the Sorcerer (1982)
Quest for the Mighty Sword (1990)