Honesty - The game doesn't seem to care if you lie to people (insofar as you don't "speak proudly"), as the only way to raise or lower this is through the reagent sellers. The game states that they are blind, therefore they ask you to count out your money for them after you make a purchase. If you pay the amount they ask (or more), this goes up. If you cheat them on the price, it goes down a lot. (Addendum: Stealing chests will also lower Honesty)
Valor - The grindiest of all, as it may randomly raise by 1 point each time you kill an "evil" enemy (orcs, thieves, pirates, sea serpents, etc). It goes down if you flee from a battle, so try to avoid that if at all possible. For these reasons, you should probably wait until you've done most of the other Virtues before you try to complete Valor.
Compassion - Giving money to beggars is the most obvious method. The other is to allow non-evil creatures (Snakes, spiders, bats, seahorses, etc) to flee from battle once they start to retreat. Starting a fight with a non-evil creature will lower it.
Honor - Giving money to beggars will boost this, as will being honest to the reagents sellers. Locating the runes and stones is the quickest and easiest way though, since that entails "completing a quest". Stealing chests, starting a fight with non-evil creatures and (especially) cheating the reagents sellers will lower it. In short, don't be a dick and this Virtue should be easy to raise.
Justice - The same raising/lowering methods as Compassion and Honesty. Don't cheat the reagents woman, let non-evil creatures flee if they attack you, don't steal, and don't initiate a battle with non-evil characters.
Sacrifice - Having a party member fall in battle will boost this one slightly. A much quicker method is to donate blood at the healers, which they will start to ask you about once you reach level 4. Fleeing from enemies or refusing to donate blood will lower it.
A way to exploit this can be found in Lord British's castle. Just have Lord British heal you to full, then stop by the healer's to donate blood until he won't take anymore. Then have LB heal you again. Rinse and repeat until your Sacrifice virtue is maxed out.
Spirituality - This one's pretty hard to screw up. Simply talking to Hawkwind in Lord British's castle will raise it slightly. Entering a shrine and meditating for one to three cycles will also boost it. Entering a shrine without meditating, meditating on the wrong virtue or using the wrong Mantra at a shrine will lower it.
Humility - You have to talk "humbly" to people when given the chance. Just say "no" when people ask if you're "the most honorable" or something like that. Doing the opposite will lower it. Fortunately, the game doesn't stop you from just finding one person who you can talk humbly to and answering their one question over and over again, so this is fairly easy to raise.
In Part 4, we'll attain all eight parts of the Avatarhood, then we'll do a bit of preparation for our venture into the dungeons in search of the three-part key.