I started playing this game as a Paladin during my Ultima series playthrough, and now I find myself constantly over-encumbered with everything.
Are Paladins really this terrible in UU, or do they improve with time? It takes forever to kill some monsters without magic and my gear gets damaged very badly in the process.
Any help with what kind of skills I should invest in, and how to increase weight-capacity would be greatly appreciated.

Your class selection mainly determines your stat range and starting skill options, so it isn't specifically an issue with being a paladin.

If you're having trouble killing things then you need to improve your weapon skill (specializing in one type is a much better approach than trying to dabble in many), and it sounds as though your defense skill could also stand some improvement. The "attack" skill is less significant than the other two, although if it's very low and your weapon skill is high then it might be worthwhile (solely because low skills tend to improve by 2-3 points at a time while high skills usually only improve 1 point at a time).

Otherwise, your skill investment mainly comes down to the sort of things that you're finding difficult to deal with.

--

As for encumbrance, it's vital to be selective in what you carry around with you. You can usually establish a 'base camp' somewhere and use it to store the things that you don't immediately need (gold, extra potions, etc). Relocate the base camp as necessary (once you're on level 6, you don't want to have to run all the way back up to level 2 each time), and consider moving the silver sapling to the same area (as long as it's a safe zone).

What is your Paladin's STR? It should be as close to 30 as possible when you create your character, since stats can't be improved during play.
Also, use the shield spell to increase your defense during combat.

Stats can be improved during play. you need to build your experience then go to the ankh shaped area on lvl 1. There you will find a shrine if you meditate at the shrine using 1 of the 8 mantras, 1 for each of the 8 virtues.(see ultima 4 for a list) Your stats will rise depending on which one you use.

No, praying at shrines will increase your skills (attack, defense, search, mana, casting etc), not your stats (Str, Dex, Vit etc). You will get more hit points during level ups, though.

I simply recreate new characters till I get one with a high Str, since that is the only stat that really matters in this game because it defines how much one can carry.

Then this is very bad. My STR is at 17, something that should put me in a lot of trouble in the future seeing how I can barely carry my own equipment plus some plot items with 1 talisman, and I'm already Level 12 or something!

Are there ANY work-arounds for this major screw up?

Well, 17 is really low, but the game can be won that way too.

First you wanna reduce your load.

Switch back to leather armor or maybe chain mail. Try to get magical armor (Rodrick the Chaos Knight has a magical chain mail). If you're having trouble during combat because of low armor class buff yourself with protective spells (Resist Blows, Missile Protection, Iron Flesh etc).

Drop the plot items (talismans that you don't actually use) in an easy to reach spot. Don't carry too much gold around. Drop most of the coins at Shak's. Don't carry too much food and potions around.

And you wanna specialize while training your skills. You need attack, defense and one weapon type. Also mana and casting since a lot of skills can be substituted by magic. Also: mana does regenerate, health does not. So cast a healing spell every now and then or visit the healing fountains on the first levels.

Also, sorry for the double post, but I just found another new issue : after re-entering the 4th level of the abyss I just encountered this grim error message - "Underworld Internal Error - Problems in Object list"

I am using the SB Pro fix/patch from Pix's Ultima Patcher, and no items have disappeared so far!

Is switching back to chain armor really vital? It's a huge blow to me in role-playing terms, having played all previous Ultima installments with full plate armor.

No double post, I sneaked in between. ;-) UW can be buggy with items (which is why I don't like to drop important items on the ground, hence the high strength). I had experienced that error message a few times too. If nothing important is missing you can continue the game. I wouldn't pick the fourth level to drop important items, though.

On the other hand that may be a good excuse to start the game anew with another character and higher strength and now, that you probably know the specialized mantras, it will be significantly easier too. Plate armor is heavy. If you find another way to lose weight, then do that. Changing armor probably is the most effective way.

Hmmm, this is definitely a tough pill to swallow. I absolutely can't live without plate armor, I've tried restarting the game now, and I feel very, very uninspired to go through all that stuff I just got over with in my week of playtime.
However, I love the fact that monsters are easy to kill and that I have plenty of weight capacity.

Gods damn it, I'm not built for this kind of moral dilemma!

(PS: Thanks a lot for the help. I'll try one of those solutions)

Well... there are a couple save editors here that you could try. If you want to avoid cheating... I don't have a solution.

You could decide to add a point (or 2 or 3...) to your Str and subtract a point (or 2 or 3...) from another stat to keep the same point total.

Another option, that adds a bit of a "payment" to the idea is to add two points to Str for each stat and then subtract 3 points from each of them.

Is the main quest timed, will i run out of time if im not quick enough or is it not time based at all?

ok thankyou