Intuitive explanation of GSVA analysis
The most intuitive explanation is  also explained in the background section:


  Conceptually, this methodology can be understood as a change in coordinate systems for gene expression data, from genes to gene sets.


Which I think it is explained in Figure 1 of the paper, which is also one of the most informative I found about the methods of an algorithm1.

I'll will use it to explain what's going on.


Fit a distribution function per gene



  For each gene expression profile ... a non-parametric kernel estimation ... function is performed.


I can't give more detail because I haven't understood it fully


Then they are normalized to make the ranks symmetric around zero

It is an inline formula between equations 2 and 3.
The Kolmogorov-Smirnov like random walk statistic is applied to those kernel estimations normalized distributions. 

Which two distributions does it compare? The genes in a gene set and all the others (but I'm not totally sure)

The role of random walk is explained a bit later from your quote:


  [the random walk] produces a distribution over the genes to assess if the genes in the gene set are more likely to be found at either tail of the rank distribution


Which is later used to calculate the enrichment score by looking the maximum deviation from zero, or by summing the largest and the lowest deviations. 


To address some other questions:


  GSVA calculates sample-wise gene set enrichment scores as a function of genes inside and outside the gene set, analogously to a competitive gene set test




1: Try finding which fittings and approximations are done inside limma