If someone is looking for pet, with a preference for a mammal that can be housebroken, with a naturally vegan diet (herbivorous), what common animals would they want to consider?
The only mammals you'd be able to keep healthy on a vegetarian diet would be rabbits, or rodents like gerbils, hamsters, mice, rats, guinea pigs, etc. They will all do fine on a diet of vegetables and grains.
If you have the means to, you could keep an exotic pet like a fruit bat. But I would stress that bats are high maintenance, might require a license depending on where you live, and aren't able to be housebroken. The first question you have to ask is are you willing to have a bat fly around your house all night?
Otherwise you'll want to look into animals like birds, fish, or even a select few reptiles.
Other mammals are either carnivore (all meat), omnivore (some meat), or insectivore (almost all insects).
I would consider looking into a house rabbit - they are wonderfully engaging little critters, can be litter trained and enjoy veggies. However, they do take considerable care and research beforehand - I highly recommend http://rabbit.org/ (the House Rabbit Society) for helping you make your decision. We have three dwarf lops that we are just crazy about!