This was bugging me and I did not want to train until I knew how things worked so I spent a few hours investigating. The answer is a bit complicated because dexterity and intelligence can effect combat and magic non linearly. The Ultima 7 Strategy Wiki is where I got most of my information.
What you want to train depends on how you play the game. If you play the Avatar as a spell caster then you want to train intelligence/magic. If you play as a melee or ranged fighter you want dexterity/combat and strength/combat. dex/combat > str/combat for both melee and ranged. All NPC parry members should only train dex/combat and str/combat they do not need int or magic.
If you want to improve your parties fighting skill then combat is the stat you need the most. This is because combat determines if an attack will succeed in hitting the target. If you have low combat you will miss often and will sometimes hit other party members. Which is a great way to die quickly. If you can't hit monsters you will obviously not win battles, so combat is by far the most important stat.
To train combat you should use a trainer that does both combat and dexterity. This is because combat is derived from dex, 1 point of dex gives you 1 combat, and because of the non linear "rubber band" effect. The rubber band effect happens when your combat is less than their dexterity and you train both dex and combat at the same time (or Strength and combat). It will cause your combat to increase by an amount proportional to the difference between your dex and combat. The lower your combat and higher your dex the greater the amount your combat will be increased. For example Spark starts off with 10 combat and 22 dex, if you train with Chad they will increase to 18 and 24. Combat increased by 8! The maximum of any stat is 30 so 8 is huge!
Intelligence and magic also have a rubber band effect.
Strength is also important because it determines how many hit points you have and how much you can carry.
Based on the above I recommend training with Chad in Moonglow (far south of the island) for dex/combat, Menion in Serpent's Hold (farthest south building/shop) for strength/combat, and for spell caster Avatars use Inforlem in Terfin or Perrin in Yew.
There seems to be another effect besides the "rubber band" going on, when I trained Iolo with Chad he gained 5 combat every time, even when combat was >= dex, but other characters did not have this happen. Some trainers might "like" some characters better than others but I have not found any others that do this.