I am assuming you are aware of generating random numbers and about RGB color values.
Color.FromArgb[
^] method allows you to create colors by specifying RGB color values. Please, read upon the third and the fourth overload of that method in the above link. By generating random numbers from 1 to 255 for each of these fields, you can create random colors more than a million or so.
Hope this helps :)