In picking a bank, it may be good to know about the difference between traditional banks, and the Postbank. The latter uses the post-offices as its outlets, there are no branches as such. It used to be popular for its low costs, and still most Dutch people have accounts there. Of the traditional banks the ABN-AMRO seems to be the most popular. In terms of services and costs, differences between the different types of banks are gradually disappearing.
You should be able to open your bank account with just your passport (or some other sort of identification) and your work contract. Among various other branches and banks of course, in the centre of Leiden are :