Yep, old thread, but since someone has resurrected it and now we have a suggestion for fruit I have to add:
My first Lab would work her little heart out for bits of fresh grean beans from my garden. My agility instructer and all the other people were amazed.
A fruit I like is apples cut into about 1/2" chunks and left out to dry on the counter for a few days. They shrink to about 1/4" chunks and dry out so you can carry them in a pocket or bag without a wet mess.