Принципиальная разница в уровне абстракции.
Nat "на лету" изменяет поле ip адрес в пакетах проходящих через устройство.
Proxy устанавливает соединение с клиентом , а потом от имени себя транслирует запросы клиента в исходящую сеть(Например в интернет), хотя бывают прозрачные прокси.
Отсюда следует следующие.
Технология Nat относительно легкое решение , однако она умеет делать только одно менять ip адреса.
Прокси это уже программа , и вариативность что она делает с трафиком гораздо больше. Может кешировать запросы, может следить за списком белых сайтов, и сопостовлять этот список с пользователями AD ,и считать рарешенный объем трафика. В общем это уже сервис. Это имеет свою цену, в плане затрат на вычислительные ресурсы.
UPD. СОбствено область применения у этих технологий разная.
Nat используется как инструмент организации сети, для экономии адресного плана, скрытия адресов, организации пипринга.
Proxy это сервис для конечных пользователей , серверов для организации доступа к каким либо ресурсам.