I think you are under the belief that men operate under a different power level structure here, when in fact men simply occupy more levels than women over all. The weakest man and the weakest woman are roughly equal, but there are more strength levels for men as a whole (thus the ++ levels). Matching Aviendha's work at the river simply means he's roughly the same level as she is, or, given his strength with Air, he could actually be weaker overall, but still skilled enough to match her feat. Egwene is 4 levels below Nynaeve, but there is no way Nynaeve could match her cuendillar ability. Naeff is shown to be similar with Air. We know he has less strength than Nynaeve, but his ability with Air is clearly meant to be amazing thus he can match her.

I think the text from Merise's conversation with Cadsuane makes it pretty clear that Narishma is as strong as she is after his most recent jump in Power, if he was still weaker than she was she would not have commented on it IMO. And it seems he gained a pretty significant increase from the time he bonded her as she seems surprised by how quickly he moved up to her strength.

Not true that men would need to be a level 13 to Travel. It's stated outright under the "gateways" entry in the Companion that "the minimum strength required for making a gateway of useful size, large enough to walk through, was 19(7). The minimum strength required to make any gateway at all out of a circle was 21(9)". Androl's Traveling talent is specifically called out in this entry so it seems true for men as well as women. There is no mention that this would be different for men than women. All we know here is that there would be a higher percentage of men who fall into this strength level or higher because men are generally stronger than women, but not always.

I suspect most of these men probably are stronger than level 19, but that's the highest we can reliably place them without more information from the text.

I assume you are trying to include the "dexterity bonus" thus making a man stronger by several levels than a woman who can perform the same OP related task, but without a scale for both dexterity and strength it's impossible to say how this works.

We know that Level 1 female is roughly equal to a ++1 male, but we don't know that a level 2 female is more effective than a level ++2 or if a level 3 female could be more effective than a level ++2 male. There is some disparity between the dexterity bonus and strength because a level 66 man and a level 66 woman are roughly equal.