É difícil dar uma resposta com dados concretos sobre esta questão, mas posso falar da experiência pessoal de ciclismo em vários países da Europa Oriental (não na Roménia, mas na Polónia, Eslováquia, Hungria, Bulgária, Sérvia, Macedónia, Kosovo ...)
O tráfego, especialmente fora das cidades, é em geral agradável. Isto é principalmente porque o tráfego é menos denso na Europa Oriental, do que na Europa Ocidental. Mas as pessoas tendem a dirigir rápido em estradas sinuosas. Apenas certifique-se de ficar no lado direito da estrada e tudo deve ficar bem. Para mim, não me senti menos segura do que a Itália, mas mesmo na Itália há uma enorme variação. Senti-me muito mais seguro nos Alpes do que, digamos, Napoli.
Considerando o risco de roubo, você está, na minha opinião, excessivamente preocupado. Pode acontecer, é claro, assim como acontece em qualquer lugar. Mas normalmente os lugares remotos são os mais seguros a esse respeito, enquanto são as cidades que representam o maior risco para a criminalidade.
Meu conselho seria abordar o aspecto da segurança exatamente da mesma forma que você fez em viagens anteriores e focar em questões mais importantes: encontrar rotas legais, etc.