I then tried putting the array into an arraylist, which reduces big-O since each object is "touched" only once, and I can use .Contains which is more efficient than iteration (not sure if that's true; I just sort of remember reading it somewhere).

As was mentioned in the comments, for your purpose, there is no significant difference in performance between int[] and ArrayList. Both store their data in a similar way, and both will have to iterate through the array to check for Contains. So that doesn't help anything.

Sorting

You mention sorting in the title of your question. But you don't actually do any sorting. Let's look at the challenge:

Write a function that, given an array A of N integers, returns the smallest >positive integer (greater than 0) that does not occur in A. For example, given A = [1, 3, 6, 4, 1, 2], the function should return 5. The given array can have integers between -1 million and 1 million.

We need to know whether 1, 2, 3, etc are in the input. You can do this, by checking each and every option, one at a time. Since you don't know whether 1 would be at the start, or at the end of the array, you have to check the entire thing each and every time. That's inefficient.

However, if you sort the input, the array becomes somewhat predictable. You can loop through the sorted array until you find the first positive number. Is it higher than 1? Then we can return 1, since that is the smallest possible integer that's not in the list - the smallest positive integer is >1 after all. If it equals 1, we can go to the next element and check its value. If it is another 1, move on. If it is >2, we can return 2, else we must move on. And repeat.

In that way, what we have done, is sorting the array (O(n logn)), and then looping through it once. All in all, that's still O(n logn).

public int solution(int[] a) {
  // sort
  Array.Sort(a);
  var answerCandidate = 1;

  // Find the first nonzero positive number.
  for(var index = 0; index < a.Length; index++) {
    if (a[index] < answerCandidate) {
      continue;
    } else if(a[index] == answerCandidate) {
      // Oops, we found our candidate in the list, so we move to the next one.
      // Since the list is sorted, we know the next one can only be farther
      // on in the list, so we don't need to restart the loop.
      answerCandidate++;
    } else {
      // In this case a[index] > answerCandidate. This means that we haven't found
      // the candidate in the list, so we can return answerCandidate. Break so
      // that we can handle the case where we pass the end of the array at the same time.
      break;
    }
  }

  return answerCandidate;
}

We can still make a marginal improvement by searching for the first positive number using a binary search on our sorted list.