I agree with Trepak - don't name a character based on personality. Names are given by the parents, so even if a person is archaic, stiff, conservative etc, her name might still be Rainbow Horselove if her parents were hippies :)
But other than that, I think both Odessa and Olena could work. Isn't Odessa a city by the coast of the Black Sea in Ukraine? Personally, I prefer Odessa.