"Most men are faster than most women" is potentially a little ambiguous, but I would normally interpret the intent of it to be that if we look at random parirings, most of the time the man would be faster -- i.e. $P(M_i<F_j)>\frac12$ for random $i,j$ (where $M_i$ is 'time for the $i$-th male' etc).
Of course other interpretations of the phrase are possible (that's what ambiguity is, after all) and some of those other possibilities might be consistent with your reasoning.
[We also have the issue of whether we're talking about samples or populations... "most men [...] most women" seems to be a population statement (about a population of potential times) but we only have observed times that we seem to be treating as a sample, so we must be careful with how broad we make the claim.]
Note that $P(M_i<F_j)>\frac12$ is not implied by $\widetilde{M}<\widetilde{F}$. They can go in opposite directions.
[I am not saying you're wrong in thinking that the proportion of random M-F pairs where the man was faster than the woman is more than 1/2 -- you're almost certainly correct. I am just saying you can't tell it by comparing medians. Nor can you tell it by looking at the proportion in each sample above or below the median of the other sample. You'd have to make a different comparison.]
That is, while the median man may be faster than the median woman, it is possible to have a sample of times (or a continuous distribution of times, for that matter) where the chance that a random man is faster than a random woman is less than $\frac12$. In large samples the two opposite indications can each be significant.
Example:
Data set A:
1.58 2.10 16.64 17.34 18.74 19.90 1.53 2.78 16.48 17.53 18.57 19.05
1.64 2.01 16.79 17.10 18.14 19.70 1.25 2.73 16.19 17.76 18.82 19.08
1.42 2.56 16.73 17.01 18.86 19.98
Data set B:
3.35 4.62 5.03 20.97 21.25 22.92 3.12 4.83 5.29 20.82 21.64 22.06
3.39 4.67 5.34 20.52 21.10 22.29 3.38 4.96 5.70 20.45 21.67 22.89
3.44 4.13 6.00 20.85 21.82 22.05
Data set C:
6.63 7.92 8.15 9.97 23.34 24.70 6.40 7.54 8.24 9.37 23.33 24.26
6.18 7.74 8.63 9.62 23.07 24.80 6.54 7.37 8.37 9.09 23.22 24.16
6.57 7.58 8.81 9.08 23.43 24.45
(The data are here, but being used for a different purpose there -- to my recollection I generated this one myself)
Note that the proportion of A's < B's is 2/3, the proportion of A < C is 5/9 and the proportion of B < C is 2/3. Both A vs B and B vs C are significant at the 5% level but we can achieve any level of significance simply by adding sufficient copies of the samples. We can even avoid ties, by duplicating the samples but adding sufficiently tiny jitter (sufficiently smaller than the smallest gap between points)
The sample medians go the other direction: median(A) > median (B) > median (C)
Again we could achieve significance for some comparison of medians - to any significance level - by repeating the samples.

To relate it to the present problem, imagine that A is "women's times" and B is "men's times". Then the median men's time is faster, but a randomly chosen man will 2/3 of the time be slower than a randomly chosen woman.
Taking our cue from samples A and C we can generate a larger set of data (in R) as follows:
n <- 300
F <- c(runif(n/3,0,5),runif(n-n/3,15,20))
M <- c(runif(n-n/3,7.5,12.5),runif(n/3,22.5,27.5))
The median of F will be around 16.25 while the median of M will be around 11.25 but the proportion of cases where F < M will be 5/9.
[If we replaced the n/3 with a binomial variate with parameters $n$ and $\frac13$
we'd be sampling from a population where the median of the distribution of F is at 16.25 while the median of the distribution of M is at 11.25. Meanwhile in that population the probability that F < M will again be 5/9.]
Note also that $P(F<\text{med}(M))=\frac23$ and $P(M>\text{med}(F))=\frac23$ while $\text{med}(M)<\text{med}(F)$ (by a substantial distance).