well veggie/cheese wise, i would recommend either of:

 - Chick peas drained in salt water and paprika and grilled in the oven for about 10 minutes
 - portabelo mushrooms cut into large chunks
 - fried halloumi
 - large chucnks of celery sauteed in salt pepper, and chilly