It's pretty impressive that for a small city, Victoria has two excellent vegan restaurants:
Green Cuisine (560 Johnson Street / 250-385-1809) located in Market Square is a self-serve, pay by weight buffet. This place would be appreciated by vegetarians, and health conscious eaters. This is THE place in town for vegan desserts, including vegan Nanaimo bars, soy ice cream, and the fantastic mudpie bars. Students get a 10% discount. They also sell their own tofu, seitan & tempeh products at a great price.
Lotus Pond (617 Johnson Street / 250-380-9293) is about the polar opposite of Green Cuisine. It is a Buddhist vegan Chinese restaurant. The food is very flavorful, and I suspect, not always the healthiest (sweet & sour fried soy balls). During the work-week, they have a lunch buffet, pay-by-weight, and after 2:30 pm it is 50% off. It's located on Johnson between Government and Douglas.