Как это было у меня (КТ + их вечерний безлимит):
Взял комп (AMD k6-2 210 Mhz, 128 RAM, 4Gb HDD), купленный вместе с монитором за 300 рэ.Воткнул 2 сетевухи. Поставил Slackware 12 без графики (3 часа). Далее пару часов настройки роутинга/фаервола (разбирался попутно) и поднятие SSHD. После этого поставил ящик на место между локалкой и провайдером. Все остальные действия производил со своей рабочей машины по SSH.
Почему слакварь? Потому, что дистр не распухший, труевый и хардкорный :) Можно и Gentoo и Debian. Про Debian ничего не скажу - не пробовал, а Gentoo - 3-4 дня на сборку на медленной машине. В принципе любой, который ты сможешь лично контроллировать (не SUSE с его YaSTом)
Далее по желанию поднимаются прокси, файлопомойка, вэбсервер, фтп и т.д.
з.ы. про анлим от КТ давно писал в отдельной теме
Мы аналогичный АМД разогнали до 266 и поставили Puppy, довольно шустро маслает. Теперь вот думаем как ловчее применить эту конфигурацию:)