Mars: Second, People have to Live.
The second thing for a Mars Colony is to understand that PEOPLE HAVE TO LIVE.
The assumption that colonists will have to be vegan (not just vegetarian) assumes a lot of things about what can actually be produced usefully in greenhouses. Seeds are inefficient. Grains. Nuts. Anything that takes a full growing season to ripen into the form we want to eat it. Anything that grows on trees or vines is inefficient. Anything perennial or seasonal is going to be inefficient and expensive. It will still need to be done, however, and trial and error (also expensive and inefficient) to see what grows well. And even then, the food results will be an occasional treat to break the monotony of rabbits and rabbit food, ie., salads and rabbit stew.
Bread? Only on Sol Prime bozo. The most reasonable thing for Mars is a paleo-diet.
Rabbits are probably the most obvious first livestock and staple protein source. They eat the plant parts that people don't want to eat, the stems and leaves and roots and leftovers. They produce hides and can produce "wool" for textiles (not much, but enough for a nice pair of soft socks for special occasions). And people can eat them. Rabbits are no-waste contributors.
Egg producers are a bit trickier. Chickens need grains and would require dedicated feed crops instead of just waste and leftovers, though they are pretty much omnivorous. Ducks can be better egg producers even than chickens but need more protein. A plus to ducks is that getting enough fat in the diet will be vital and ducks produce a lot of fat. Geese are larger, lay far less well, but are mostly vegetarian, and also very fatty. Quail are bred for egg and meat production and may be a Mars staple simply because they're small. The best bet is probably to go with minimum populations of all four and see what works. Feathers can be used for stuffing pillows, or art and down for blankets or jackets, eggs are a good protein source and open up all sorts of culinary options, fat in the diet keeps brains from atrophy, and Mars gets its Christmas Goose.
And last? Goats. I'm tempted to say pigs because... bacon... but I have to go with goats. Goats are small, efficient, they eat all the plant odds and ends that rabbits eat, people can eat them, they can produce wool for textiles, leather, and milk. Milk means cheese. Milk means ice cream. It makes most sense to raise goats for milk first and wool second and meat only last.
Because people need to live. And one of the most important social elements of being human is eating. Colonists may be sick to tears of another bowl of rabbit stew or yet another salad, but being able to look forward to real bread on Sol Prime (Sunday) and to the occasional bowl of quail egg soup, pudding, mayonnaise or melted cheese, will go a long way to keeping people sane.
That and a couple of community cats and finches in the atrium.