Keep in mind that dealing with coin collectors is one of the biggest pains a teller has. Especially if the teller is not a coin collector. If the teller is a coin collector then you probably don't want to be going to them.
I have a great relationship at my bank. The tellers call me when they get stuff in that I look for. When I am ready to supply a lunch I ask the branch manager which day will be good with everybody there. It is usually a Friday. Then I do things like order pizzas, letting them order subs and then I pick up the order and deliver it or sometimes I just buy a $5 Subway gift certificate for each of them. They always appreciate it.