It turns out that you can do very slightly better than the dice in your example. The probability has to be a multiple of $1/36$, your example has $20/36$, and the best possible value is $21/36=7/12$.
From my answer to the question that anon linked to, we know that the probability of one $6$-sided die beating another while having a lower median can be at most $3/4-1/12=2/3=24/36$. Wikipedia gives an example of a cycle of four dice in which each die beats the next one with this probability.
You're looking for a cycle of three dice in which each die beats the next one with the same probability. Without loss of generality we can assume that the dice carry $18$ different numbers. Then there are $18!/6!^3=17153136$ different sets of dice, so it's well within the reach of our electronic friends to try them all out. Here's code that does that (rather inefficiently). The result is that the maximal probability for such a cycle is $21/36=7/12$ and there are eight different sets of dice that attain that probability. Here they are, with consecutive stretches of numbers collapsed into one as in your example:
0 3 3 3 6 6
2 2 2 5 5 5
1 4 4 4 4 4
0 0 3 3 3 6
2 2 2 2 2 5
1 1 1 4 4 4
0 3 5 5 5 5
2 4 4 4 4 7
1 1 1 6 6 6
0 3 5 7 7 7
2 2 4 4 6 9
1 1 1 8 8 8
0 3 3 5 5 5
2 2 2 4 4 7
1 1 1 6 6 6
0 3 5 5 7 7
2 2 2 4 6 9
1 1 1 8 8 8
0 3 3 3 3 5
2 2 2 2 4 7
1 1 1 6 6 6
0 0 3 6 6 6
2 2 2 5 5 5
1 1 1 4 7 7
There are two sets with $7$ different numbers, four sets with $8$ and two with $10$, and your near-optimal example has $9$, whereas the mean number of different numbers after collapsing, averaged over all sets with $18$ different numbers, is $18-17\cdot(5/17)=13$, so consecutive stretches of numbers and thus high collapsibility are a striking feature of these sets.
P.S.: I just realized that there's a symmetry in that you can invert the orders of both the dice and the numbers and get another set with the same probability. The first two sets are related by this symmetry, as are the third and seventh, the fourth and sixth and the fifth and eighth. Thus there are only four really different sets of dice, with $7$, $8$, $10$ and $8$ different numbers, respectively.
The probability that you roll 4+ is the probability that you roll a 4, a 5, or a 6. Each of these events has probability $\frac{1}{6}$; so, the probability of rolling 4+ is $\frac{3}{6}=\frac{1}{2}$.
For your other scenario, note that the event that you get a 5+ when you are allowed on re-roll can be broken up in to two disjoint events: event $A$, in which you roll a 5+ on the first try; and event $B$, in which you roll a number 1-4 on your first attempt, and either a 5 or 6 on the second.
Then $P(A)=\frac{2}{6}=\frac{1}{3}$, since this is the event that you roll either a 5 or a 6. For $B$, we have
$$
P(B)=\frac{4}{6}\cdot\frac{2}{6}=\frac{2}{9},
$$
since you must roll a 1, 2, 3, or 4 on the first attempt and either a 5 or 6 on the second. So, overall, the probability of getting 5+ when you allow one re-roll is
$$
P(A\text{ or }B)=P(A)+P(B)=\frac{1}{3}+\frac{2}{9}=\frac{5}{9}.
$$
(Note that we have used here that $A$ and $B$ are disjoint possibilities.)
So, you are more likely to get a 5+ with a re-roll allowed than to get a 4+ with no re-roll.
Best Answer
The possible combinations are not equi-probable. For instance it is more probable to have 3 dice in 3 known different quadrants than in a single one. You can not get the probability of a combination by taking the inverse of the number of combinations. So your result $\frac{1}{16}$ is correct.