I am resurrecting this thread to reveal the results of some research. Not many definites yet, but I am starting to get some ideas. This is a run that would almost certainly have to made completely through multiple times to really figure things out. Anyway, here's the goods:
-There shouldn't be a lot of random battles. The key should be obtained early, even if it means stealing from towns. The penalty for stealing is pretty low and only affects easily-raised virtues. That lets you get into hythloth and get the balloon. Then you can fly around with no random encounters. Furthermore, you can fly to cove and get gate travel! Finally, the dungeons go pretty fast when you know what you're doing.
-Figured out the issues with getting Tremor. The flags that control spell availability at Spells Unlimited are single bits in $68d3 and $68d4. The lowest bit of $68d4 is tremor. Now some of the spells are revealed in pieces by multiple NPCs, but I believe that only one conversation actually sets the flag. So among the three NPCs who mention the man in black that knows tremor ......*NONE* of them sets the flag!!! The flag actually gets set when you talk to a mage in Lord British's Castle who says "Disturb me not, for I seek to end odd-order intermodulation in linear power stages." This is great because it is an easily accessible spot that doesn't even require the key. In fact, you have to go right by there to get the rune of spirituality.
-Undecided whether it's better to start with paladin or mage. Paladin starts out with much more experience - 325 vs 175. This is significant because you only need 400 to reach level 4. It's necessary to get the ship eventually to get a few items and reach the final dungeon. However, in most cases, the balloon can replace the ship for transportation. This is probably even preferable as it eliminates random encounters. There are still a lot of mandatory dungeon battles, certainly enough to get the 225 exp for the mage. But there's another issue with the valor virtue that may make it preferable to do more random encounters. Mage starts out in Moonglow and so she can get herbs for magic right away and use fire to nail small fry for exp and gold. The paladin can sell his starting armor and buy a bow, then gate to Moonglow or walk to paws for herbs. Then again, the mage can put this money towards the key.
-You can increase your MP through the following loop:
--Enter hythloth from Britain Castle
--Cast exit immediately
--Re-enter the other entrance
--Touch the orb two steps from that entrance. This kills you but raises all stats by 5. Paladin gets 5 MP, Mage gets 10. Didn't check druid.
--You get revived by Lord British and you're in his throne room. There's no impact to your virtue or exp, but your gold gets reset to 400.
--Repeat as many times as necessary. This is probably about four times for a paladin. Of course, this would work well with multiple party members. Each would touch the orb and die before the main char does so. Everyone would get high MP to tremor the crap out of all the dungeon battles.
-I went through all the towns and castles and did a few other things to see how I can build the virtues. They start at 50 and you need to go up to 99. Three of them are problematic: Valor, compassion and sacrifice.
--It seems that the only way to raise valor is to fight. It goes up one point every battle, along with a point of honor. Also, it does not go up in the battle rooms in the dungeons, only on random encounters. If anyone figured out a better way to raise valor, please speak up! If I am right about this then a solo run is probably best as there are going to be a lot of random battles -- at least 49.
--Compassion only goes up when you give money to a beggar. It doesn't matter how much, 1 gold is just as good as 1000. You get 5 points either way, and one point of humility. The ghost near the rune of valor gives 5 points for talking to it, but it disappears afterwords.
--As was noted before, sacrifice only goes up from giving blood. You get 6 points of sacrifice and 3 humility.
--Other virtues are easy. Honesty, justice, honor and humility go up just by giving the right price to the item vendor. You can also sell an item for the right price. To facilitate this, you can buy a bunch of staffs and cloths early on and sell them off over the course of the run. As with other things, there's a timer, but it seems to be separate for herbs and weapons. Meditating at shrines increases spirituality. There are also several NPCs that can raise these 5, the best being the reaper in British's castle.
--By the way, using the skull drops all virtues by 10. However, if this causes them to go below 10, they get set to 10, so 10 is effectively the lower limit. Still, unless there's a better way to get valor the cost is way too big.