How far west are we going in this thread? Because if we're counting Hungary as eastern rather than central Europe (which I know is historically/culturally debatable), then one of my favourite bands comes from there - Thy Catafalque. Sensational avant-garde metal band; clean vocals that would be enjoyable for the folks who run the other way from death growls and really catchy, often keyboard-led melodies that aren't cheesy like all that shit in goth/symphonic metal.
Also, all the Porcupine Tree fans out there should check out a couple of Polish bands, Riverside and Indukti. I'm actually not into them much but there's a huge fan crossover there; I know I'm in something of a minority (which isn't to say I dislike them).
Ukraine has given us plenty of great metal bands as well, of which probably the greatest export is Drudkh - fans of Agalloch, get on practically anything Drudkh's ever released. They've also recently done a side project with Neige of Alcest called Old Silver Key, which is truly phenomenal heavy shoegaze. And just next door in Romania is Negură Bunget, who play fantastic black metal and I'm pretty pissed I missed seeing them on their Aussie tour last year, since I was in New Zealand at the time. On a much more palatable note for most of this forum, I listened to an album for the first time today by Grimus, an indie/alt rock band from Cluj; it was called Panikon and seemed pretty promising on first listen.
As for Russia itself ... they've got a number of quality post-rock bands such as Mooncake and I Am Waiting For You Last Summer. Also, surprisingly enough, the best witch house band on the planet comes from Murmansk - Vagina Vangi. Both 2011 EPs are absolute quality. Okinawa Lifestyle (from Georgia, not Russia) are another decent band straddling the line between witch house and chillwave.
The one other Russian band I'm a huge fan of are death/doom metallers The Morningside; again, Agalloch fans should LOVE their debut, and their second album would appeal even more to Katatonia fans. The debut is one of my favourite metal albums. Immense, epic, and sprawling.
Beyond that, I guess I need to hurry the fuck up and listen to some of Vlad's recommendations. I rather enjoy that one Мумий тролль album that I have; need to spin it a bit more.