How random is Random.Next()?

You are not testing for cycles. You are testing for how long it takes to get a random number you've had before. That's completely different. Your figures are spot on for testing how long it takes to get a random number you had before. Look in wikipedia under "the birthday paradox" for a chart of the probability of getting a collision after a certain number of iterations.

Coincidentally, last week I wrote a blog article about this exact subject. It'll go live on March 22nd; see my blog then for details.

If what you want to test for is the cycle length of a pseudo-random number generator then you need to look for not a number you've had before, but rather, a lengthy exact sequence of numbers that you've had before. There are a number of interesting ways to do that, but it's probably easier for me to just tell you: the cycle length of Random is a few billion, so you are unlikely to be able to write a program that discovers that fact. You'd have to store a lot of numbers.

However, cycle length is not the only measure of quality of a pseudo-random number generator. Remember, PRNGs are not random, they are predictable, and therefore you have to think very carefully about what your metric for "randomness" is.

Give us more details: why do you care how "random" Random is? What application are you using it for that you care? What aspects of randomness are important to you?

You are assuming that the randomness is better if numbers are not repeated. That is not true.

Real randomness doesn't have a memory. When you pick the next number, the chance to get the same number again is just as high as any other number in the range.

If you roll a dice and get a six, then roll the dice again, there is no less chance to get a six again. If you happen to get two sixes in a row, that doesn't mean that the dice is broken.

The randomness in the Random class it of course not perfect, but that is not what your test reveals. It simply shows a phenomenon that you get with every random number generator, even if actually creates real random numbers and not just pseudo-random numbers.