How about some syntax sugar for IEnumerable<>?

public interface IReadOnlyCollection<T> : IEnumerable<T>

{

    int Count { get; }

}

No it wouldn't have to support index-based access. Just look at ICollection<T>: you can enumerate it (via IEnumerable<T>), it has a Count-property, but also an Add(T)-method and some additional members (like Remove() and IsReadOnly). Yet it doesn't have index-based access. That's what IList<T> is for.

Now: IEnumerable<T> « ICollection<T> « IList<T>
What I'd like: IEnumerable<T> « ICountEnumerable<T> « ICollection<T> « IList<T>

Actually, I didn't say (or mean) that I wanted IEnumerable<T> to have a Count-property: IEnumerable<T> is perfectly fine the way it is. I myself have recently writen a tokenizer that has a method ReadAll which returns an IEnumerable<T> that lazily reads from a TextReader and produces tokens. In this case, a Count-property would mean that all the tokens would have to be read before anything can be done.

What I want is that there was an interface IReadOnlyCollection<T> or ICountEnumerable<T> the my classes can expose in cases where my classes know the number of elements. I never indicated index-based random access. In fact, read-only index-based random access could also be exposed as an interface IRandomAccessEnumerable<T>. Adding these 2 additional interfaces would not break existing code (because the existing code would not know about them). The interface hierarchy would then look like this:

public interface IEnumerable<T> : IEnumerable
{
IEnumerator<T> GetEnumerator();
}

public interface ICountEnumerable<T> : IEnumerable<T>
{
int Count { get; }
}

public interface IRandomAccessEnumerable<T> : ICountEnumerable<T>
{
T this[int index] { get; }
}

public interface ICollection<T> : ICountEnumerable<T>
{
void Add(T item);
void Clear();
bool Contains(T item);
void CopyTo(T[] array, int arrayIndex);
bool Remove(T item);

bool IsReadOnly { get; }
}

public interface IList<T> : ICollection<T>, IRandomAccessEnumerable<T>
{
int IndexOf(T item);
void Insert(int index, T item);
void RemoveAt(int index);

T this[int index] { get; set; }
}

Actually, now that I think about it further: it could be a good idea to move all the members of ICollection<T> and IList<T> that can be performed on read-only collections to interfaces IReadOnlyCollection<T> and IReadOnlyList<T>. It would allow for richer API's without additional overhead. The current collection classes would not have to be changed. The only thing that changes is the addition of these interfaces and the modification of ICollection<T> and IList<T> (so they implement IReadOnlyCollection<T> and IReadOnlyList<T>).

public interface IEnumerable<T> : IEnumerable
{
  IEnumerator<T> GetEnumerator();
}

public interface IReadOnlyCollection<T> : IEnumerable<T>
{
  int Count { get; }
  bool Contains(T item);
  void CopyTo(T[] array, int arrayIndex);
}

public interface IReadOnlyList<T> : IReadOnlyCollection<T>
{
  T this[int index] { get; }
  int IndexOf(T item);
}

public interface ICollection<T> : IReadOnlyCollection<T>
{
  void Add(T item);
  void Clear();
  bool Remove(T item);
  bool IsReadOnly { get; }
}

public interface IList<T> : ICollection<T>, IReadOnlyList<T>
{
  void Insert(int index, T item);
  void RemoveAt(int index);
  T this[int index] { get; set; }
}