I think the good people here have covered most of your questions for a conventional visit to Russia.
One thing that always gets me about Russia is Moscow. It's an interesting place, but by visiting Moscow alone, or basing your view of the country on your experience of Moscow, I don't really think you're seeing the 'real' Russia. It's just like visiting London: interesting city, but it doesn't give you much feeling for what England is at all. As Paul Theroux says, 'A capital city should be the last city you visit in a country, not the first'. I personally have never warmed to Moscow very much, though it has improved a lot in recent years. Saint Petersburg is a more likeable place (apart from the climate), but it was always modelled as a European city and is a visual anomaly. I should say on the other hand that despite its huge size, Russia is a very, very centralised country and that everything of political, cultural and economic importance (apart from the extraction of raw materials) happens in Moscow and St Petersburg. If it's museums, theatre, art exhibitions etc. you want to see, then you'll want to base yourself here.
I fell in love with Russia when I first visited in 2007, and have been going back regularly ever since. I fell in love with the people and landscapes, less so the cities. I travel in my own vehicle, which makes things easier. I've visited all but three of Russia's regions. Western European Russia is not a place of dramatic landscapes, but there are some very scenic locations; the beautiful 'Saviour on the Nerl' Church in Bogolyubovo (just outside Vladimir), or the shores of Lake Nero around Rostov. Also Suzdal as was mentioned above, and some of the crumbling small towns around there. This is also Russia's cultural heartland (although Kyiv is in fact the origin of Russian Orthodox tradition, when the Byzantines first brought Christianity to pagan Rus' in the tenth century) and an easy place to access. Yaroslavl, Vladimir, Kostroma are good options to visit here.
The Volga River is something like the backbone of European Russia; Kazan is worth seeing, and there are cultural attractions at Sviyazhsk and Bolgar. Russian's write-off many of the cities on the Volga such as Samara, Tolyatti, Ulyanovsk as being grim and industrial, but I really love the area around them and the Volga has a certain magic about it.
If you are heading north, Novgorod is just about the oldest city in Russia, and worth seeing. Further north, Karelia and Murmansk region have some very beautiful landscapes indeed, but they are fairly sparsely populated and a dead-end unless you plan to continue into Finland or Norway.
If you want to head west, then Pskov and Smolensk are lovely, though in general the western border regions of Russia are not very interesting.
Heading south, you pass into Russia's fertile black soil region; the land of the old feudal estates. Many of Russia's celebrated writers and poets had estates here, which are now museums. Further to the south is the Don Region and beyond that the Caucasus Mountains; unquestionably the most dramatic landscapes in European Russia. Culturally they are fascinating, but probably not what I would recommend as a first glimpse of Russia.
You could also be more unorthodox and base your first trip in Siberia or the Far East. Here it's much more about the landscapes than history or culture and the republics of southern Siberia (Altai, Khakassia, Tuva, Buryatia) have some of Eurasia's finest scenery. The people of Siberia are famous for being friendly and extremely kind (not that Russians in the west aren't) and you'll easily make friends if you stay in a place for a while. But here it really pays to have your own transport as the cities are often not very interesting. Exceptions in my opinion would be Irkutsk, Tomsk and Vladivostok. Every now and again however, one finds an idyllic place such as Verkhoturye in Sverdlovsk Region, or Severobaikalsk at the north of Lake Baikal; even far-flung Magadan was a highlight (very personal choices obviously). You could base yourself in one place such as this, make some local friends and learn far more about Russian people and culture than by rushing around between cities on an itinerary. The language barrier may be a problem here: you could use Couchsurfing to meet local English speakers.
I hope this has given you a bit more of an idea of the dizzying number of options out there, but want mostly to say that there is far, far more to Russia than the two big cities.
EO