eu tenho preferencia pelo slackware ou freebsd, mas acho que o debian seria ótimo pra ti.
para montar um proxy squid qualquer distribuição que não seja voltada apenas para desktop serve muito bem.