DH and I are vegetarian. We find lots of good options at AK. Love Tusker House and look forward to trying SC in Pandora, which looks very veggie friendly. There are also good quick service options in AK, Mr. Kamal's is all veggie, I think.
MK is harder. BOG, if you can get it, has a good quinoa dish, salads and veggie soups.