De maneira geral sempre que puder usar a propriedade `Count` é melhor porque o acesso é direto. A expectativa é que ela sempre seja O(1).

[`Count()`][1] é um método de extensão do LINQ, portanto só pode usar em objetos que implementem `IEnumerable` que poderá executar algum algoritmo para obter a contagem. Se o objeto em questão implementar a interface `ICollection` o que ele fará é justamente ler a propriedade `Count`, o resultado será o mesmo e o tempo de resposta quase idêntico, mas bem ligeiramente mais lento por ter uma indireção. Mas ambos terão complexidade O(1). Note que isto não é garantido usando este método, depende do contexto.

O [fonte dele pode ser visto no Reference Source do .NET Framework][2]. [Veja também do .NET Core (.NET 5 pra frente)][3] (tem que fuçar nos arquivos parentes já que ali está mais organizado.


  [1]: https://msdn.microsoft.com/en-us/library/bb338038(v=vs.110).aspx
  [2]: https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,1191
  [3]: https://source.dot.net/#System.Linq/System/Linq/Enumerable.cs,577032c8811e20d3