I started learning Russian as a hobby about a year go. Learning cryllic is easier than it looks. Also the whole gender thing is a lot easier with Russian than with French, German etc.. because you can tell what gender a word is is just by its ending (most of the time). But once you get into cases, grammar, sentence structure etc..it's pretty much a mindfuck. I can't compare it to Eastern Asian languages since I've never tried to learn them, but it's not easy and it gets very frustrating. I still can't hold a conversation or understand fluent Russian, though I do go through long periods of slacking.
Oh yeah and when you're beginning, make sure you use like 5 different sources to learn the alphabet/pronunciation, and try to find audio files etc.. because every place I look there are slight variations. Some sites/books say "yo", some say "yaw", some don't mention that "o" and "e" are pronounced different depending on where they are in a word etc..
Here are a couple sites I found useful
http://www.russianlessons.net
http://www.masterrussian.com/
http://www.youtube.com/watch?v=dlJw08uMvE4&feature=PlayList&p=62077C49F5A58BEE&index=0 (This guy is pretty awesome, he's got a huge series of lessons that start out with the alphabet and eventually go into somewhat more complicated stuff. I think he's Polish so don't take his pronunciation as perfect)