Random numbers in C#

I've learned, over the last few days, a very disturbing thing.

Say you want to make a random number. Or pseudorandom, since most of us don't have radiation sources and the readers necessary to record such noise.

Now, say you're using C#.

Yay! They've made a Random class. You can just do:

Random r = new Random();
int theRandomNumber = r.Next();
int anotherRandomNumber = r.Next();

Yay! Problem solved!

But wait.

Suppose you've put this code in, say, a constructor, one that gets called a few times. Now you have a problem; it turns out, the constructor will make the exact same random number generator, with the exact same seed value! How do I know this? Because I just lost three days and a huge number of hair follicles to this problem.

Here's the deal:
1) MainObject makes, say, an array of ContainedObjects.
2) ContainedObjects all call the random number generator as above during startup.
3) Each random number generator has the same seed.
4) So, the 'random' sequence is mimicked in each of the ContainedObjects.

Technically, I suppose it's still random, much like a random number generator that always returns 4.

How do you fix this problem?

1) Seed with the tick count. Apparently, this is a bad idea, because it doesn't work consistently. After testing on three different machines with three different clock speeds, using DateTime.Now.Milliseconds may or may not return the exact same milliseconds. Not sufficiently random, not a solution.
2) Uptime of the computer. I have no idea how to get this.
3) Have the MainObject hold the random number generator. However, it now needs to be a member; how many times do you initialize an array of ContainedObjects? If it's more than once, but the random number generator is initialized the same way again, then you're back to the same problem. Heaven forfend that you need multiple random numbers throughout the place; you'll need to make your random number generator global! Global variables make my skin crawl.
4) I don't know. I'm currently doing option number 3, and it hurts my head, but at least it's just a member in MainObject.

What's the lesson in all of this?

Be careful of random number generators you don't write yourself. One of Knuth's exercises is to check the random number generators in programs in the nearest computer lab; apparently, the C# guys didn't check out what he had to say.