Now HERE'S a probability problem

Batman is really Bruce Wayne

First, we need to solve a slightly different problem:
What if there were only 415 cards - 208 red, and 207 black?

Each of the 415! permutations can be divided into one of four groups:
(a) First card red, and reds > blacks after every card
(b) First card red, but at some point, reds = blacks
(c) First card black, but at some point, reds = blacks
(d) First card black, and blacks > reds after every card
Note that (d) is impossible, as reds > blacks after card 415
For each permutation in (b), let N be the first card where blacks = reds; notice that it has to be the opposite color of the first card, as otherwise there would be some number < N where blacks = reds
Switch cards 1 and N; the first N cards are the same, so blacks = reds after card N, but now the first card has changed color, so if it was a type (b) permutation, it is now type (c), and vice versa.
Thus, for every type (b) permutation, there is a matching type (c).
Since all permutations beginning with black cards are type (c), the number of "bad" permutations = 2 x the number beginning with black cards, and the probability of a permutation being bad = 2 x the probability of it beginning with a black card; in this case, 2 x 207/415 = 414/415.
The probability that a permutation has reds > blacks after every card is 1 - 414/415 = 1/415.

Now, to solve the original problem.
If the last card is red, then there will be 208 black and 207 red cards after card 415.
If the last card is black, this reduces the problem to the 415-card problem.
The probability of the last card being black = 1/2, so the probability of reds > blacks after every card from 1 to 415 is 1/2 x 1/415 = 1/830.