> А как с помощью APT'а добиться функционала urpm-package-cleanup в плане удаления
> старых ядер?

Посмотрите apt-scripts -- если бы мне такое было нужно, то:
- убирал бы ядра из Allow-Duplicated в apt-conf и накропал вариант list-extras;
- или вообще обошёлся ещё более простой логикой на шелле.

Впрочем, у меня нет такой нетерпимости к старым ядрам -- я-то уже знаю, зачем они бывают полезны на практике.  Хотите, продолжайте бегать и хвастаться фичей, которая может оказаться сомнительной, а может просто завести в ловушку.

> Можно ли как-то граф зависимостей построить?

Уже несколько человек упомянули apt-cache dotty, посмотрите на досуге.

> И как найти и удалить пакеты, которые ставились руками и из сторонних репозиториев?

apt-get install apt-scripts
apt-cache list-extras
(ещё полезно list-nodeps)

> Про Apt pinning знаю, знаю, как с его помощью задаунгрейдить систему.
> Но вот как описанного функционала добиться? Спрашиваю потому, что не
> так хорошо знаю apt/dpkg.

http://www.altlinux.org/Downgrade (правда, это apt-rpm, но базовый синтаксис /etc/apt/preferences вроде не пострадал).