I usually run Bobbit or Human Paladin, Elf Thief, Fuzzy Wizard and Bobbit Cleric, myself, but there are likely better parties. That's just my favourite.
With two healers, I can indefinitely support a poisoned or starving party, which is a problem that's come up more than once. The Thief is how I make money in the early game, until I can get in behind the armour stone in the Death Gulch, which requires keys and a boat.
In terms of healers, I actually like using a Druid; if INT is at least 18 and WIS is at least 20, it's like having two healers in one character. This tends to work well before I am ready to use dungeon fountains for healing (which are the only realistic way to heal 2000+ HP later in the game).
Personally, I don't like running Humans, Dwarves, or Bobbits because they can't reach 99 DEX, and with anything less, misses become annoying. That's actually the main problem I have with Paladins; they can't reach 99 in both DEX and WIS, making them not so great in the long run. In fact, I have been known to make Fuzzy Paladins (though I should point out that, endgame, Wizard spells are more important than Cleric spells).
I actually don't use Death Gulch for money; I have found that looting Perinian works well. Just put your thief-type (I happen to like Rangers because they are good for so many other purposes, but a Thief will work very well for this purpose), use a ladder up/down spell to reach level 3, loot the areas near the corners, and then go down the southeast corner to reach an area with more treasures. I find this to be pretty fast, and it doesn't require keys or a boat; only torches (which are much cheaper) and magic (which can eventually replace torches).
One other thing I have noticed is that, in Ultima 3, and unlike many other games (certainly unlike Might and Magic 3-5), it is actually a reasonable strategy to switch party members mid-game. If you can get a lot of money, it is easy to raise a new character's stats. XP isn't hard to get if you have a Wizard with 70 INT; just cast spell O (Necorp, which reduces every enemy to 1 HP), and your new character can easily finish off the enemies in one hit; the guard near the entrance of Death Gulch is a good choice. (If the new character is your first Wizard, get 75 INT and spell P will help that character get experience.)
Also, I note that, in the final dungeon, the only difference between classes that matters is the ability to cast spells; hence, at that point, Thieves are tied with Fighters and Barbarians for being the worst class. Fortunately, as I mentioned above, it is easy to train a replacement once you reach the point where that matters.
Edit: Corrected Druid stats.