Краткий ответ: 16 х 16 пикселей.
Длинный ответ:
.ico-файлы на самом деле могут содержать несколько изображений с разной глубиной цвета - вы можете предоставить 16x16, 32x32, 48x48 и 64x64 в одном файле, и ОС выберет лучший для показа.
Конечно, чтобы сохранить небольшой размер файла, вы не хотите помещать в него слишком много файлов, но если вы думаете, что люди могут сохранять ссылку на своем рабочем столе (скажем, это веб-приложение), то это, вероятно, хороший шаг.