This method selects a random element from an Enumerable with only one pass (O(N) complexity). It contains optimizations for argumens that implement ICollection by using the Count property and the ElementAt LINQ method. The ElementAt LINQ method itself contains optimizations for IList.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Extensions
{
    public static class EnumerableExtensions
    {
        private static Random random = new Random();

        public static T SelectRandom<T>(this IEnumerable<T> sequence)
        {
            if (sequence == null)
            {
                throw new ArgumentNullException();
            }

            if (!sequence.Any())
            {
                throw new ArgumentException("The sequence is empty.");
            }

            //optimization for ICollection<T>
            if (sequence is ICollection<T>)
            {
                ICollection<T> col = (ICollection<T>)sequence;
                return col.ElementAt(random.Next(col.Count));
            }

            int count = 1;
            T selected = default(T);

            foreach (T element in sequence)
            {
                if (random.Next(count++) == 0)
                {
                    //Select the current element with 1/count probability
                    selected = element;
                }
            }

            return selected;
        }

    }
}

//
// Usage:

int[] ints = new[] { 1, 2, 3, 4, 5 };
Console.WriteLine(ints.SelectRandom());

IEnumerable<int> seq = Enumerable.Range(1, 5);
Console.WriteLine(seq.SelectRandom());