Langton's Ant simulation
Optimisation


  I use a Stack where I push my Squares.


A stack is the correct data structure when you want last-in-first-out behaviour. Is that the behaviour you need here?


  It works great until 106 (takes 5 minutes to run).


That is a long way from "great". 106 shouldn't take 10 seconds. Use the right data structure for the task, which here is something with amortised constant time insertion and lookup.

Other notes


public class Square { 
        public int x, y;
        // White = 0, Black = 1
        public int color = 0;
}



Why are all of the fields mutable? Why is there no explicit constructor? Rather than using a 32-bit type to store a single bit and needing to document the legal values, why not use a 1-bit type (i.e. bool isBlack)?




int color = 0;



Does this need such a wide scope?




for (int i = 0, counter = 0; i &lt; 10000000; ++i, ++counter)



What is the purpose of counter? As far as I can tell, it isn't used anywhere.




        squares.Push(new Square() { x = 0, y = 1, color = 1 });



...


        squares.Push(CreateSquare(x, y, 1));



Why the discrepancy?




        orientation = Rotate(orientation, color == 0 ? true : false);



condition ? true : false is an unnecessarily long way of writing condition.




    if (orientation == Orientation.NORTH) y += 1;
    if (orientation == Orientation.EAST) x -= 1;
    if (orientation == Orientation.WEST) x += 1;
    if (orientation == Orientation.SOUTH) y -= 1;



This is precisely the kind of thing that switch statements were invented to handle.




    // if null create one and rotate
    if (s == null)
    {
        squares.Push(CreateSquare(x, y, 1));
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }else if(s.color == 1)
    {
        s.color = 0;
        orientation = Rotate(orientation, false);
        steps.Add(orientation);
    }else
    {
        s.color = 1;
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }



Don't repeat yourself. This could be refactored as

    if (s == null)
    {
        s = new Square { x = x, y = y, color = 0 };
        squares.Push(s);
    }

    orientation = Rotate(orientation, s.color == 0);
    steps.Add(orientation);
    s.color = 1 - s.color;





            blackSquaresAt100k = squares.Where(sqa =&gt; sqa.color == 1).Count();



Count has an overload which takes a condition, so enumerable.Where(foo).Count() can be refactored to enumerable.Count(foo).