people
if you go to places with less tourists, it is easier to get into contact with people. If you don't speak Russian, it is a good idea to go to a university or other places where you are likely to find people that speak English. in Forums like couchsurfing and hospitalityclub you can find local people that want to meet with travelers. It could also be interesting to see both Western and Eastern Ukraine and get an impression about the differences. An invitation to a dacha would probably be interesting for you;)
soviet legacy
In addition to Kharkov, Pripyat (Chernobyl excurtion) is like a time machine exploring an abandoned Soviet provincial town.
historical places
Lviv old town is a winner. If you want to party you will have to start early though as things are rather quite and close rather early. I agree that Chernivtsi.
I also think that the advice to move on to see Moldova is a really great advice. Chisinau is probably the only European capitol that you stand a fair chance to see meet a cow on the street. Or what about 5 liters of home made wine for a dollar or so (remember to bring your own can:). Transdnistria, the countryside and excurtions to wineyards and monastries are some other highlights. It is easy to include from Odessa or from Lviv/Chernivtsi.
I enjoyed these books on Ukraine:
http://www.amazon.com/The-Ukrainians-Unexpected-Nation-Edition/dp/0300154763/ref=sr_1_1?ie=UTF8&qid=1335279342&sr=8-1
have a great trip!
J
