Подскажите, пожалуйста: правильно ли я понимаю, что в комплект документов на отказ от гражданства должны входить апостилированный Einbürgerungzusicherung и нотариально заверенный NE?

На EBZ обязательно, на NE не всегда, зависит от консульства.

- где можно поставить апостиль на EBZ и какие сроки по опыту? Можно ли сделать это быстро?

Зависит от федеральной земли. Например, апостиль на EBZ в Хессене обычно ставят автоматически в Regierungspräsidium еще до выдачи, в BaWü апостиль тоже ставится в Regierung/Regierungspräsidium соответствующего земельного округа (в BaWü их 4). У нотариуса нельзя поставить апостиль на оригинал EBZ.

Какая у Вас федеральная земля?

- где можно сделать перевод NE, чтобы данный перевод считался официальным? Кто должен заверять данный перевод - может ли это сделать обычный нотариус в Германии или только консульство?

Переводы для российского консульства можно делать самостоятельно. правильность переводов обязательно должен заверить российский нотариус, в Германии такие есть в консульствах. Немецкий нотариус, разумеется, ничего такого сделать не может.