Nautilus Pompilus is a Russian band. Their genre would be classified as "progressive rock". They had many albums, some dealing with politics, some dealing with heartbreak, some dealing with life. An interesting thing about this band is that they switched vocalists (and even their style of music) several times.
Generally, they were most popular during the mid 80s and early 90s, although they are still around. In my opinion, their best album is definitely Knyaz Teshini. It has some superb songs, such as Ckovanie Odnoi Tsepyo, which is a symbolic song about communism, beautifully written, with a hint of satire and excellent guitar and synthesizer parts. Knyaz Teshini itself is also an excellent song, with a nice beat and a good synth part.
I would strongly recommend getting this album if you can understand Russian. If not, then you won't appreciate it that much, obviously because you will fail to understand the lyrical content, which is a key part. If you are willing to learn Russian, then listening to Russian bands (including Nautilus) would obviously help. Knowing Russian isn't a requirement however. Most Americans that I know who have listened to this album enjoyed most of the songs on it. It just requires a diverse musical taste.