We consider the column subset selection problem, that is, the problem of selecting a few representative columns of a matrix in order to construct a good low-rank approximation. We present a randomized algorithm, based on an adaptive leverage score sampling strategy, which guarantees, in expectation, an approximation error that matches the optimal existence result in the Frobenius norm. Our method, called Adaptive Randomized Pivoting (ARP), can be seen as a randomized counterpart to a recent deterministic approach proposed by Osinsky. Although the same theoretical guarantee can be achieved with other methods, such as volume sampling, ARP is simpler and less expensive. We will highlight how this simple yet powerful strategy can be adapted to a range of other tasks related to low-rank approximation, including the Discrete Empirical Interpolation Method, cross/skeleton approximation, and the Nyström approximation of positive semidefinite matrices.