Ananda in Gazcue, Ojas in Zona Universitaria, Govinda off M?ximo G?mez are vegetarian but far from gourmet.
I've heard good things about a place in Ciudad Nueva but can't remember the name.
Para T? in El Mill?n is a very popular Taiwanese tea garden with some delicious vegetarian dishes on the menu, and a long list of natural juices and teas. Good prices too.
Two others are Jardin Verde in Naco and Raices off M?ximo G?mez.
Org?nica in Agora Mall does tasty veggie snacks but it's very expensive.