One point worth mentioning - I've had a gmail account for around 18 months and never had genuine spam. The only messages (less than half a dozen) in my Spam Folder during that time were false positives.
I'd thoroughly recommend gmail.
Conversely, you're going to get a lot of daily junk with Yahoo and Tiscali.