Pra obrigar os clientes a usar o seu proxy, a forma mais simples é (supondo novamente que o servidor proxy seja também o gateway) desabilitar o compartilhamento da internet:
sudo sysctl net.ipv4.ip_forward=0
Mas isso pode causar efeitos colaterais importantes (programas como Outlook, Thunderbird, ping, traceroute/tracert e outros que não podem usar o seu servidor proxy simplesmente vão parar de funcionar). A alternativa é bloquear a passagem de qualquer porta relacionada com o tráfego web:
iptables -A FORWARD -m state --state ESTABLISHED,RELATED -j ACCEPT
iptables -A FORWARD -m multiport -p tcp -s $REDE_INTERNA --dport 80,81,82,443,444,8080,8000,8008,8443 -j REJECT
iptables -A FORWARD -s $REDE_INTERNA -j ACCEPT
iptables -A FORWARD -j DROP
Claro que isso deixa uma brecha pra que seus usuaŕios naveguem usando um servidor proxy externo numa das portas não bloqueadas.
Uma alternativa mais efetiva é bloquear todas as portas, e liberar só as necessárias:
iptables -A FORWARD -m state --state ESTABLISHED,RELATED -j ACCCEPT
iptables -A FORWARD -m multiport -p tcp -s $REDE_INTERNA --dport 25,53,110,143,123 -j ACCEPT
iptables -A FORWARD -m multiport -p udp -s $REDE_INTERNA --dport 53,123 -j ACCEPT
iptables -A FORWARD -p icmp -s $REDE_INTERNA -j ACCEPT
iptables -A FORWARD -j DROP
Caso você use alguma aplicação que não possa passar pelo proxy (e.g. Conectividade Social da Caixa Econômica), vc precisa definir regras adicionais de exceção.
Ainda é possível fugir do seu proxy usando um proxy externo em uma das portas liberadas; a única forma efetiva de impedir isso seria usar um firewall de camada 7, o que não é nada simples de implementar.