>> Очень вкратце -- rpm более "дубовый", dpkg более "инженерный".
> Что вы вкладываете в эти слова? Если по гибкости и настраиваемости, rpm
> далеко впереди.

В rpm давным-давно были сделаны вещи вроде проверки контрольных хэшей и подписей -- в dpkg их очень долго не было (сейчас точно не помню, расскажите кто?).

В rpm зависимости скорее однозначны, а "вилки" разруливаются через виртуальные пакеты -- в dpkg реализованы булевы.

В rpm идёт сборка шелл-скриптами (хотя можно переопределить buildshell) по предопределённым секциям spec-файла -- в dpkg сборка на make плюс шаблоны (причём сборку с повторяющимся шаблоном на вагоне dh_* красивой у меня язык назвать не поворачивался).

Для расковыривания .rpm нужен хотя бы rpm2cpio -- для .deb достаточно coreutils.

Пакетные скрипты в .rpm неинтерактивны по определению (хотя технически можно занять stdin и повисеть) -- в .deb подразумевается возможность запуска (в т.ч. интерактивного) debconf.

Есть множество различий, в каждой точке выбор неоднозначен и тенденции для rpm/rpm и deb/dpkg мне в сумме кажутся именно "дубовыми/продуктовыми/энтерпрайзными" и "инженерными" соответственно.  Что ни капельки не противоречит их происхождению.

PS: поймите, я не ругаю то или это.  Просто разные взгляды на схожие задачи.
PPS: насчёт производительности при разрешении зависимостей как раз не знаю -- надо бенчмаркать, но ни в коем разе не судить по времени отрабатывания соответсвующей фазы аптом.