Первая строка ICollection<User> users = new Collection<User>();
создает ссылку на объект (Collection), который реализует интерфейс ICollection, тогда как вторая строка Collection<User> users = new Collection<User>();
создает ссылку на объект, который является конкретной реализацией класса Collection, где T = User.
В терминах использования вы должны использовать ссылку ICollection, когда ваш последующий код должен быть независим от типа коллекции, с которой он имеет дело, то есть вы можете предоставить любой объект, реализующий ICollection, и ваш код все еще будет работать. Прекрасно, если ваш код не тесно связан (что мы все хотим, конечно).
Использование Collection в качестве ссылки тесно связывает ваш код обработки с классом Collection, конкретной реализацией ICollection, и хотя вы все еще можете использовать только методы, определенные в интерфейсе, вы можете также использовать некоторые специфические функции класса, и тогда вы выиграете не сможет легко заменить объект коллекции чем-то другим. Для этого есть веские причины, но это немного выходит за рамки ответа здесь, поищите здесь «Внедрение зависимостей» и «Инверсия управления», и я уверен, что вы найдете множество фоновой информации.