Во-первых, обратите внимание на то, что теперь можно на НонСтоп выкладывать снимки до 150 Кб.
Во-вторых, стоит иметь ФотоШоп начиная с версии 7,0 (её вполне достаточно)
Итак, Например, Фотошоп
Сначала делаем всё, что надо, с исходником (уровни и т.п.). Я бы у этого снимка средний бегунок в уровнях сдвинул бы до 1,5. Потом уменьшаем размер в пикселях - Изображение\Размер изображения. Проверяем галку "сохранять пропорции". Ставим высоту, например, "500"\ ОК. Затем делаем Аншарп Маск: Radius - 0.5 ... 0.8 px, 50...100% (редко больше 80%). Затем Файл\Сохранить для Web. Тыкаем закладку "2-Up", cтавим галку в "Optimized", открываем тут же (круглая кнопочка) меню "Optimized", выбираем пункт "Optimize to file size" и ставим чуть меньше 150 (148, 149) - ОК .(а можно подбирать "Quality" в районе 70-90% и одновременно следить за тем, чтобы не выйти по весу за 150 Кб.) Затем - Save.

Рецепт, приведённый выше, кастрированный - "Аншарп маск" очень важен, т.к. при уменьшении размера снимок ещё более замыливается и с этим надо бороться.
Кстати, при "высветлении" этого Вашего снимка (он действительно слишком тёмный), его мыльность становится очень заметной. Он, наверное и в оригинале был не шибко резким, а уменьшение ещё и усилило эту проблему.