as for accomodation (no idea if you're still looking for some but the thread is far too long for me to read it all):

accomodation in moscow is horridly expensive (there's only one youth hostel i guess). so expect to spend some 30 to 50 dollars a day in that minimum. in st-petersburg, things are hardly better.
a room at a babushka's would be 10 to 20 dollars a night, i guess.

as for other cities, i don't really know but i guess old soviet hotels are not over expensive -but also terrible and depressing.

russia, as opposed to almost all countries in europe has a very bad infrastructure for tourism. they clearly make a lot for rich expats and wealthy tourists and obviously don't care about backpackers and other visitors. i hope it will change in years to come.
the visa also is a huge problem when you want to stay more than 2 weeks in the country and travel around a bit (registration is officially the worst pain ever but i know authorites are getting a bit cooler and lenient now).

things are improving...slowly. apart from that (but that is a big issue), the country's great and people usually are extra nice when to get to know them except for some sellers who simply don't give a damn about you. i remember once when i was at one of these big train stations in moscow(leningradskiy or kazanskiy), i almost had to apologize to the lady at the counter because she didn't want to give me information on the pskov-riga train!!!