That is a provocative suggestion! Gaiman presents a rather provocative sexual politics with this scene. I think you are right in comparing the prostitute’s client with King Solomon, as Gaiman expresses a subtle contempt for the mainstream religious images of Judeo-Christianity, and his derogatory depiction of this character, Bilquis’s sordid lover/victim, could well be a poke at old Sol. Bilquis swallows her client whole through her vagina in the act of sex, an extraordinary image which seems redolent of a primal female power exercising authority over a weak and false male representative. Of course, the mythic Bilquis was the Queen of Sheba, and her power vis-à-vis King Solomon of Jerusalem is a matter of some debate.
This mythic rebalancing of gender power also seems intended to illustrate other areas in which Gaiman suggests our society is unbalanced. Notably, the pagan Gods such as Thoth and Odin have an intuitive natural wisdom which has been forgotten by the arrogance of modern views. This is a completely post-modern world that Gaiman envisions, with the self-perception of identity of the USA subject to mockery and derision in the eyes of the forgotten gods who linger in the margins of the dominant culture.