Правильно ли я понимаю базовый алгоритм деплоя?
1) На DO я как бы арендую себе комп, который будет моим сервером, верно? Потом устанавливаю туда, скажем, nginx, и трачу пару ночей и кучу нервов на настройку.
Да.
VPS - Это, с одной стороны, что-то вроде виртуальной машины, кучу которых можно запускать/останавливать на одной физической. С другой стороны, все, что говорят про более низкую производительно ОС в виртуальной машине (по сравнению с ОС на живом железе), это практически не относится к VPS (причина - разные принципы виртуализации).2) Нужно будет скинуть на сервер исходники моего проекта, например, посредством клонирования репозитория с github'а. И зависимости установить + со статикой разобраться. Статику сам nginx должен раздавать, а не django (использую этот фреймворк), тк это эффективнее.
При разработке на интерпретируемом  языке это неизбежно.3) Этот сервер будет иметь IP-адрес, через который он будет доступен для 'внешнего мира', и можно будет этот IP привязать к купленному домену.
Да.4) Для связи с сервером лучше иметь Линукс на локальной машине.
Управление сервером идет по SSH. ОС на локальной машине может быть любая. Из-под Windows, например, можно работать через PuTTy.
Посмотрите на mne.ru, у самого там 2 виртуалку. 256mb ram - 90р/мес., 512 - около 170