Я слышал, что раньше это стоило примерно 800€.

Даже больше, 900 с копейками, только это было очень давно. Когда я выходила из гражданства (11 лет назад), было уже 300 с чем-то.

Пожалуйста, расскажите чего далее ожидать.

Ну, собственно, если всё в порядке, то месяца через 4 получите справку о выходе из гражданства в обмен на паспорта (паспорта лучше заранее отсканировать, чтобы на всякий случай остались копии). Оригинал справки о выходе из гражданства ни в коем случае не надо отдавать немцам, только ксерокопию и перевод. Если в Вашем ЕБХ настаивают на оригинале, сделайте очень хорошую цветную копию и отдайте лучше её (немцы эту бумагу заберут и когда-то уничтожат, а Вам оригинал может пригодиться).

После повторной проверки Ваших документов немцы вручат Вам Einbürgerungsurkunde, с этого момента у Вас будет немецкое гражданство. Тогда можно будет отказаться от отчества и онемечить имя и/или фамилию (конечно, если хотите). И можно заказывать немецкие паспорта.