I second HSBC... I went with them after so many good recommendations from this site!
I got an account the week I arrived, was very well treated, got what I asked for, and have (knock on wood) excellent service since.
aptsyle, in regards to the fraud protection... I ring them each time I'm going out of town to let them know where I'll be, and have never had a problem. My bank in CA (a credit union) is also very stringent, but I'd rather have that. I send them a fax each time I'm going somewhere else. Again, never a problem.