I'll second both "Dersu Uzala" and "Solaris" and add Sergei Eisenstein's "Ivan the Terrible" with Prokofiev's wonderful score. I think I've mentioned this before, but many classic Russian films can be watched in their entirety on Mosfilm's YouTube channel. Click the "cc" button in the lower right hand corner of the YouTube screen for subtitles.
A belated thanks for the Mosfilm link. I always thought Eisenstein and Prokofiev should have done Ivan as an opera (as it is it's a kind of opera, only nobody sings).