If N is big enough, you're going to get some similar-looking colors. There's only so many of them in the world.
Why not just evenly distribute them through the spectrum, like so:
IEnumerable<Color> CreateUniqueColors(int nColors)
{
int subdivision = (int)Math.Floor(Math.Pow(nColors, 1/3d));
for(int r = 0; r < 255; r += subdivision)
for(int g = 0; g < 255; g += subdivision)
for(int b = 0; b < 255; b += subdivision)
yield return Color.FromArgb(r, g, b);
}
If you want to mix up the sequence so that similar colors aren't next to each other, you could maybe shuffle the resulting list.
Am I underthinking this?