Vou tentar explicar a diferença com alguns exemplos. Lendo apenas a definição na RFCRFC eu, particularmente, tenho problemas de entender o significado em termos mais práticos.
Gateway
Imagine que ele é a porta de saída para uma outra rede. Fazendo uma analogia simples, se seu computador é uma casa e a Internet fica do lado de fora, o Gateway é a porta. Sem a porta, você fica trancado na casa.
O Gateway simplesmente faz o roteamento das requisições que chega a ele para a rede interna. É por esta razão que quando você precisa acessar a Internet em casa, o Gateway é o roteador da sua residência; é ele que dará o acesso a outra rede (Internet) sem restrições.
Proxy
Ele serve para proteger a rede externa. Usando a analogia da casa, é uma forma de deixar que você veja do lado de fora da casa, mas apenas o que ele quer que você veja.
Diferente do Gateway, o Proxy consegue fazer vários filtros e redirecionamentos, permitindo ou barrando os acessos conforme ele desejar, mantendo todos os computadores da rede anônimos. Normalmente é usado por empresas para restringir/controlar o acesso a Internet.
Um servidor Proxy que recebe as requisições e as repassa sem modificações também pode ser chamado de Gateway. Comumente este tipo de Proxy é chamado de Servidor Proxy Transparente.
Tunnel
O Gateway e o Proxy agem como intermediários da conexão. Este não é o caso do Tunnel, pois os dados de um protocolo são encapsulados dentro de um outro protocolo, exigindo um software na origem e destino para enviar/receber as informações.
Usando a analogia da casa, seria como se você cavasse um túnel direto para a outra casa (rede) no qual deseja se comunicar, sem usar intermediários.
Se comparado ao Proxy, envolve menos burocracia, pois este pode exigir autenticação, pode adicionar um identificador dele no header, pode responder usando cache, etc. Já com Tunnel todas as requisições e respostas são passadas de forma intacta.
Na prática, as VPNs são um bom exemplo para entender o conceito de Tunnel.