Krylov methods are commonly used iterative methods for solving large sparse linear systems, however they suffer communication bottlenecks on parallel computers. Therefore, Communication-Avoiding methods have been developed where the Krylov subspace is built block by block, so that $s$ matrix-vector multiplications can be done before the orthonormalization operation. This paper introduces a new variation on s-step GMRES in order to improve its stability and to reduce the number of iterations necessary to ensure convergence, with a small overhead in communications. Some theoretical improvements are necessary to accomplish this, and are interesting in their own right. Namely, we develop a new block variant that allows us to express the stability difficulties in s-step GMRES more fully. Using this variant, we can create a simple adaptive s-step GMRES algorithm, where the block size is variable and increases gradually. Our numerical experiments show a good agreement with our stability analysis and demonstrate the efficiency of our original variable s-step approach.