Preamble
Most of the rationale for this answer has already been discussed by Trenin et al.
However, there are some errors.
In particular, from the original question (my emphasis), "If after game N, you have more than $1 million then you win. If not, you lose."
The opening bet of \$500 is thus not sufficient, as if this were to be followed by 85 losses, we would be back to precisely \$1 million, which counts as a loss. In terms of the puzzle design this has to count as a loss, as otherwise, a winning strategy would be N = 0, just give the million dollars straight back.
In addition Trenin's answer stated N = 86, but when I followed the same methods I was able to do N = 87, which I've now reproduced by a different method below.
A critical point is that all losing conditions are equivalent - whether the CEO is down by a single dollar or you've gambled away the whole million, so once the value of N is chosen, after N-1 losing bets the Nth bet should be for the entire remaining balance.
However, a dollar that is left until the last bet has almost no effect on the expected value - the earlier we bet it, the more the potential winnings increase our expected profit given success. (consider the possibility of adding an extra dollar to the first bet, or to the second bet... if both lose, you end up in exactly the same position for subsequent bets, but the first one should win 1/19 times, but the second wins only 18/(19*19) times, so the expected value from a dollar bet as early as possible is important).
Thus, when in a losing position each bet should be for the largest amount possible that still leaves enough funds to make all remaining bets from the million dollar float... and each of THOSE bets must be enough to win back all earlier losses and also ensure a float to make \$100 bets for the remainder of the games.
Also, as already discussed in other answers, we're better off with fewer 18:1 bets rather than more 36:1 bets (I ran this both ways, and agreed), and we also need to maximise the value of N, as each possibility to avoid indentured servitude greatly outweighs the expected gain from betting larger sums.
Construction of optimal solution
Consider the very final bet. We will bet all remaining funds in an attempt to win back all the earlier losses, with anything in excess of \$1 million being our profit, which is incidental. The next multiple of 18 above 1 million is 1000008, so we should bet 1/18 of that, which is \$55,556. This means that for the most efficient solution, the total of all preceding bets (the amount by which we are down before placing this final bet) will be \$944,444.
Similarly for the penultimate bet, we know that if we after placing this bet we'll be down \$944,444 to put us in the correct position for the final bet. The winning amount also needs to cover (at minimum) a \$100 stake for the final bet, and \$1 profit, so we need winnings of at least \$944,545 and therefore a bet of \$52,475. Thus just before the penultimate bet we should be down by \$891,969, which defines the winnings for the 2nd before last bet as at least \$892,170, etc...
Continuing this iteratively, we find that this implies that the 86th before last bet should be for \$507 at a position where we're down by \$1. In this case our winnings would be \$9,109 which covers the \$507 stake, 86 further bets of \$100, and \$2 winnings. However, this cannot be iterated further so instead we make the first bet for \$508 from the starting position.
Solution
This means we can last for N = 87 games, and the chance of losing that many times in a row is just 0.906%, so the chance of winning is 99.094%
The increasing series of stakes to use is
\$508
\$530
\$556
\$583
\$611
\$641
\$673
\$707
\$742
\$780
\$820
\$862
\$907
\$955
\$1,005
\$1,058
\$1,115
\$1,174
\$1,237
\$1,304
\$1,375
\$1,450
\$1,530
\$1,614
\$1,703
\$1,797
\$1,897
\$2,003
\$2,115
\$2,233
\$2,359
\$2,491
\$2,632
\$2,781
\$2,939
\$3,106
\$3,283
\$3,470
\$3,668
\$3,878
\$4,100
\$4,335
\$4,585
\$4,848
\$5,128
\$5,423
\$5,736
\$6,068
\$6,419
\$6,791
\$7,184
\$7,601
\$8,042
\$8,509
\$9,004
\$9,528
\$10,083
\$10,670
\$11,291
\$11,950
\$12,647
\$13,385
\$14,166
\$14,994
\$15,870
\$16,798
\$17,780
\$18,820
\$19,921
\$21,087
\$22,321
\$23,629
\$25,013
\$26,478
\$28,030
\$29,673
\$31,412
\$33,254
\$35,204
\$37,269
\$39,456
\$41,771
\$44,222
\$46,817
\$49,565
\$52,475
\$55,556
Note that these add up to precisely \$1,000,000
After the first win from any of these, we switch to making \$100 bets, and have ensured sufficient funds to do so without dipping back into the original million, thereby guaranteeing we finish in profit even if there are no other wins (which will be the case with non-negligible probability).
If my other calculations are correct (2 different methods disagreed by a few cents, and I couldn't trace any more errors), the weighted expected profit is \$-2,590.63 if we value indentured servitude at \$-1,000,000 as in the question. Considering only the winning cases I get a weighted average profit given non-loss of \$6469.71
I believe this is now fully optimal.
Towards proof of optimality (or an even better solution?)
The above construction demonstrates that this is the optimal solution under the presupposition that an optimal solution is one that requires only 1 win in N rolls of the roulette table.
However, for a complete proof of optimaility, this presupposition would also need to be proven.
If it is not in fact optimal, then the optimal solution must require more than 1 win.
For strategies requiring only a single win, we fail with probability (18/19)^N - i.e. only in the case where there was not even a single win.
For strategies requiring at least 2 wins, we also fail in at least the cases where there was precisely 1 win, so the probability of failure is (18/19)^N + (18/19)^(N-1)*N/19. In order for this to beat the single-win strategy, it would need to work for N >= 126. Far higher values of N would be required for strategies always requiring 3 or more wins.
The iterative construction for the single-win strategy can be constructed beyond 87 iterations (... and we can stick with the calculated \$507 bet rather than \$508 on that iteration), and gives the "target" that a multi-win strategy must reach. For example, when there are 87 rounds remaining with only a single win required, the pot must have at least $999,999 in it.
If a strategy requiring 2 wins exists, it needs to ensure that after the first win, we have sufficient funds to make the corresponding bet sequence from the single-win strategy. This can be extended beyond 87, for example, with 125 rounds remaining (i.e. after the first bet of a hypothetical 2 win strategy with N=126), we would need to be "down" by -\$9,921 (i.e. have at least \$1,009,921 in the pot). i.e. in a multi-win strategy, the first bets will necessarily be LARGER than the initial bets in the single-win strategy (this is compensated by the later bets being much smaller).
In order to check if a strategy requiring precisely 2 wins is feasible, we can construct one in a similar way as the 1-win strategy, i.e.
If we've only got 2 rounds left with no wins so far, we would need to win both of them. There's no point saving any money for a final bet if we lose, as we're going to be enslaved whatever happens, so we bet all remaining funds hoping to get the \$55,556 required for the final bet. That requires a bet of \$3,087.
With only 3 rounds left with no wins so far, we need to win 2 of the next 3. If we lose this one we need to leave \$3,087 for the last ditch attempt as above, but if we win we need an extra \$104,944 for the last 2 bets of the single-win strategy, so a bet of \$5,831 is required, meaning the pot must have at least \$8,918 in it before making this bet.
This can similarly be iteratively extended, and we find that this 2-win strategy works up to N = 120, at which point the probability of failure is 1.014%, higher than the optimal single-win strategy, implying a probability of success of 98.986%. Beyond 120 rounds remaining, an initial pot of more than \$1 million is required. In particular this strategy cannot work for N = 126 as required.
Similarly, a strategy requiring 3 wins can be constructed, which only works up to N = 149 with an initial pot of \$1 million, etc...
Intuitively I did not expect any strategy to outperform the optimal "single win" strategy, because every bet made reduces our expected return by 1/19 of the amount bet (which is how the casino makes its money!), and multi-win strategies would almost certainly be making more bets and/or initial bets for larger amounts.
Whilst the above does not definitively rule out every other possible alternative strategy, it hopefully makes a good start towards a more rigourous proof.
To reconstruct my "experimentation" spreadsheet
In excel, enter 1000001 in cell B1. This represents the amount needed to guarantee success with 0 wins and 0 games remaining. Cells A1 and E1 will contain zero (or can be left blank).
Enter the following on the second row:
A2: =A1+1
B2: =B1+100
C2: =B1-E1
D2: =IF(C2=0,0,MAX(CEILING(C2/18,1),100))
E2: =D2+E1
Replicate these downwards as far as you are interested in investigating.
Column A contains the number of bets that must be made, column B the amount that must be in the pot to guarantee success with 0 wins, column C the minumum amount that must be won in the current bet, column D the bet that must be made to achieve that (0 means that if we reach this point we're already doomed to failure, otherwise the minimum bet of 100 is enforced), and column E the amount that must be in the pot to guarantee success with 1 win.
I also added in D1: =A1+1 as a marker for how many bets need to be won.
Columns C to E can then be replicated to the right as required to investigate the condition for 2 or more wins required to guarantee success. e.g. column G gives the bet that must be made if 2 wins are required, and column H the amount of money needed to guarantee success with 2 wins. Both show zero when the current position is a guaranteed loss.
The first few cells in column F (and I, L, etc.) can be deleted to avoid the highly improbable end conditions - rather than saving some money right until the end so we can still win if we get two greens in a row, we can delete a few rows so that the strategy only works if the first win is before a given point. This can allow us to start from a slightly higher value of N with the same money, but gives more opportunities for the system to fail.
For any value of N, requiring at least K wins where the Jth win is within M[J] games (N, K and all M[J] being integers that define the strategy), this can easily be evaluated to find out the minimum amount of money required to guarantee being able to perform the strategy with N games remaining...
One combination that this can confirm works for N = 500 is "at least 16 wins, of which the first is within the first 100 games, the second is within 150 games, the third within 175, ... the 15th within 475 games.". This has some scope for minor optimisations, as the initial balance only needs to be 999756 with that precise combination. However, even without the side-conditions that are necessary to make it affordable from a starting pot of \$1,000,000, and which increase the probability of failure, "at least 16 wins out of 500" seems to fail more than 1% of the time. As such I did not attempt the more complex probability calculation for the overall strategy's chance of failure.
Following these and various other similar experiments with specific cases, I am convinced (albeit without a full proof, so it is possible that I am mistaken) that no strategy can outperform the "1 win in 87 games" strategy.
