Aye, GTA has always been about going where ever you want and the fact that you could swim in San Andreas made a huge difference for me, and really opened up the world more than flying did actually.
Anyway, I can certainly agree with the fact that Vice City had more style, and really captured the 80's feel better than SA captured the 90's feel. Plus lots of people were actually scared away by San Andreas' sheer size, and having so much stuff to explore just overwhelmed them. I felt that a bit in the beginning actually.
Also obviously Vice City didn't have to much elevation in its terrain, based on Miami being fairly flat (afaik anyway).