В фотошопе. Потом в png сохраняю и конверчу какой-то фриварью. И наоборот.

Фотошоп тоже имеет функцию сжатия изображений без видимых потерь. Открываешь изображение, далее --> Save for web и выставляешь качество High(это и есть порог без видимых потерь).

По умолчанию не поддерживает. Скачать плагин для сохранения изображений в формате ico можно тут например, но я не вижу смысла в этом, иконка и в gif формате может быть.

~online~,
После фотошоповского save for web jpg можно ужать процента на три обычно, а png - до двух раз. Повторюсь, картинка будет весить меньше, а выглядеть так же.

Попробуйте сами: http://punypng.com (работает в онлайне). Эта тулза в одиночку не сможет выжать два ведра сока из одного апельсина, но результаты у неё неплохие.