In Amsterdam, there are a lot of Felafel fast food places, from the Middle East (I think). All the students eat at them, and there is a policy to load up again with salad FOC. They are very tasty actually, and you will not walk out hungry, or be in need of a meal for about eighteen hours!
BTW, like you, I stayed at the van Onna last year. A great hotel on a quiet and beautiful canal, and very bike friendly. I preach to the converted...sorry. Have a great trip.
Edit: I just realised that the stuff I ate two weeks ago in Amsterdam contained no meat. Yikes!