If you're new to these games, i'd go for San Andreas, the game play is the same as the first two, but there's a lot more to see and do, you should really buy all three though, you could get the lot for about 20 quid on ebay.
I hated San Andreas! But i love my Liberty City and Vice city, Vice City will always be my favourite though!
San Andreas was too involved, especially having to work out and eat etc, if i wanted to do that, i would play the sims!
I agree with Johntheplamf, San Andreas is the best of the series.
I bought the 1st two as a double pack on the Xbox (GTA 3 & Vice city). I decided to play them in order, so I completed GTA3, then moved onto Vice City.
Only problem is the games are far too similar and I got bored and only played vice city for a bit and gave up.
When I got San Andreas I loved it and completed all the main missions. GTA is great but can get boring as the series doesn't really change much!!
So you might as well choose the best of the series which is by far San Andreas.