First, we need to establish that the historiography of Theodora and Justinian is... complicated. Our main source for their reign is this guy called Procopius, who wrote two official histories (Buildings and the Wars), as well as the Secret History. The first two are very flattering of both rulers, while the latter is not. These give us two very different perspectives on Theodora. Buildings is considered a panegyric, or a piece of literature designed primarily to praise and venerate the subjects, possibly comissioned by Justinian himself. Some have suggested this means that the official narratives are thus more flattery than truth, and the Secret History shows Procopius' true observations. However, this is complicated by how the Secret History characterizes the rulers as literal demons whose heads would leave thir bodies. Chapter 12 is literally titled, in all sincerity, "Proving That Justinian and Theodora Were Actually Fiends in Human Form."

In short, we have two accounts of Theodora, from the same author, with opposite perspectives. In one, she is a beneficient saint. In the other, she is literally born of the devil. We have a choice between heroic poetry and tabloid journalism. Having clarified this lack of clarity, let's return to your questions.

-------------------

Was Theodora a prostitute?

Probably. The main source for this is the Secret History, which called her the "Most Depraved of All Courtesans" and did its best to paint her in a very negative light. It's kinda funny - almost every biography I've read about her 1) says she was a prostitute 2) mentions the Secret History is not to be trusted 3) gives the Secret History as their source for saying she's a prostitute. In contrast, the Buildings makes a point of mentioning how, together with Justinian, Theodora "cleansed the state of the pollution of the brothels, banishing the very name of brothel-keepers, and they set free ... the women, providing them with independent maintenance, and setting virtue free."

Another piece of evidence put forward is this: there was a law saying that senators could not marry actresses. Emperor Justin (Justinian's uncle and predecessor) had to change this before she could marry Justinian. This would seem to suggest that she was definitely an actress, and most actresses were also prostitutes. However, it's worth noting that this law also applied to inn-keeper's daughters, and women in a servile position.

While I personally find the evidence that Theodora was a prostitute inconclusive, I must acknowledge there's not really any other proposed background. One guy, Michael the Syrian, says that she was actually the daughter of a priest and grew up very piously. This generally isn't taken very seriously - he was writing 700 years after her death, and had strong religious reasons to gentrify her backstory.

So Theodora's prostitute background is not proven beyond a reasonable doubt, but it is the most likely story. We are reasonably certain that Theodora was an actress, and this makes it likely that she was a prostitute. To an extent, it doesn't matter - it wouldn't change how society viewed her. Just like today, most people would generally equate 'stripper' with 'prostitute', even though they aren't actually the same thing.

Tldr: society at the time probably considered Theodora an ex-prostitute.

--------------------------

Was it her critics playing up the salaciousness of her past?

Oh, most definitely. In the Secret History, she is literally a sex-crazed lust-driven demon who wastes the citizen's taxmoney on lavish, satanic orgies. This definitely goes past the point of truth.

---------------------

Was there really so little difference in the status of those backgrounds?

(I'm uncertain what you mean by 'those backgrounds' here.)

Justinian's background vs Theodora's background:

Both had quite a rags-to-riches story. Justinian and his uncle Justin were both illiterate pig-farming peasants before Justin ended up moving up the ranks to become captain of the emperor's guards, and then emperor. This happened late enough in life that Justinian's origins were also in the peasantry. This wasn't quite as bad as being a prostitute, but he wasn't exactly tainting his bloodline at this point.

In fact, we should establish that bloodlines were nowhere near as important in this time period as, say, the middle ages. This isn't the 'Byzantium' empire; it is the (Eastern) Roman Empire. It was very much the practice of the Romans that the emperor would just pick whoever he thought would make the best heir and adopt them. The throne was definitely inherited after a fashion, but choice and meritocracy had a much larger role than we would expect. So he Justinian was definitely marrying down, but not as scandalously as you might have thought.

The bigger scandal in Theodora's background was her religion. She was a Monophysite; Justinian was Orthodox. I'll leave this whole schism out, but suffice to say that this was a major issue that tended to overshadow any other minor detail of her background.

The background of being an actress vs a courtesan vs a prostitute:

There was a difference between these groupings, but not one that mattered to most of society. I'd compare it to being a burlesque dancer, vs a high-class escort, vs a brothel girl in today's society. There is definitely a significant difference to anyone in the industry, but most people outside it would just think it's all sex work.

-------------------

Were [criticisms of her] a case of 'sexism masking policy objections'?

There actually weren't that many contemporary criticisms of her (on the basis of her prostitute background). The Secret History doesn't count; it was not widely publicised or read at the time. Secret History and all that.

Actually, the main criticism that I can think of came from Justinian's mother, the Augusta Vigilantia, who was the main opponent of their marriage. This is rather ironic since she came from peasant origins herself. It's been suggested that she was worried that this would be one taint too much, and create a large problem for her family. It's also been suggested that she just gave in to new money snobbishness. Regardless, by all accounts most objections to Theodora's background ended with the Augusta's death.

Again, this is primarily because objections to Theodora's religion took precedence. Monophysitism was not in.

-------------------------

Overall:

Theodora's possible prostitute background was, at the time, never as big of a deal as her religious leanings. The one place her whorish tendencies is discussed in detail is the Secret History, which really only discovered a reader base a millenium or so after she died. Most contemporaries considered her regal, behaving as befitting of a Queen. I actually can't think of a single incident where she was accused of being disloyal to Justinian. Even in the Secret History, it was more of an open relationship Evil-Power-Couple type thing.

------------------------------

Sources:

Procopius for pretty much all of it, with the important references in text. A reference from Michael the Syrian, but as mentioned, he's not really taken seriously.

​

Some references were taken from non-history sources: The description of the Secret History as 'tabloid journalsim' I attribute to the Extra Credit YouTube channel, but I think this is an accurate description given some of the other things I mentioned in the text. The idea that the Augusta disapproved of Theodora because of new money snobbishness came from the History of Byzantium podcast, which I'd say is pretty decently researched - actually, I'd recommend their bibliography if you want to look into this any further, it's nicely organized and with helpful reviews. That said, we don't really have any evidence for why the Augusta felt the way she did, I mostly threw that in to underline the narrative irony that the toughest opposition to Theodora's pauper background came from someone with a pauper background.