In general, memory bandwidth is improving at a slower rate than processor arithmetic speeds are improving.
In relative terms, over the years, the amount of memory that we can transfer in the same time as one CPU clock-cycle has actually decreased!
All the same issues apply to GPUs -- bandwidth often becomes the bottleneck instead of ALU cycles. Using smaller data formats can often give huge speed boosts -- as above, mip-mapping is kinda-sorta a form of data compression for the case where you're viewing a texture at a distance
It's also interesting to look at the specs of cheap vs expensive models of video cards -- often one of the things that separates them is an order of magnitude difference in their memory bandwidth! e.g. picking some nVidia cards:
GeForce 205 -> 8 GiB/s
GeForce GTX 285 -> 159.0 GiB/s
Your high-end users can process a hell of a lot more data per frame than your low-end users can, which is why the low-end cards will have to use lower-resolution render-targets and textures, lower vertex counts, etc, etc...