There are several options
Note: for my answer I will assume that you use the more stringent and more realistic "Variant: Encumberance" rules (p. 176 PHB), since your question suggests you care about such things.
If you carry weight in excess o f 5 times your Strength
score, you are encumbered, which means your speed
drops by 10 feet. If you carry weight in excess o f 10 times your
Strength score, (...) you are instead heavily encumbered, which means your speed drops by 20 feet (...)
Encumberance limits in the core rules without this optional rule are purposely set extremely lenient, as many play groups do not enjoy tracking encumberance, and with these high limits there is less chance for it to matter. If you do not use Variant: Encumberance, you can triple all the numbers in my answer for final weight that can be pulled, and pretty much any kind if medium creature will do.
How much can they pull?
As per the vehicle rules in DMG, p. 155:
An animal pulling a carriage, cart, chariot, sled, or wagon can move weight up to five times its base carrying capacity, including the weight of the vehicle. If multiple animals pull the same vehicle, they can add their carrying capacity together.
with Base Carrying Capacity under normal encumberance being (p. 176 PHB):
Carrying Capacity. Your carrying capacity is your Strength score multiplied by 15. This is the weight (in pounds) that you can carry, which is high enough that most characters don’t usually have to worry about it.
Assuming you use Variant: Encumberance, a creature at full speed can pull a loaded vehicle weighing its Strength score x 5 x 5 = Strength score x 25. Four creatures can pull a vehicle weight of their Strength score x 100 lbs.
Some creatures also have the Beast of Burden feature, for example the Mule:
Beast of Burden: The mule is considered to be a Large animal for the Purpose of determining its carrying Capacity.
Size and Strength. Larger Creatures can bear more weight(...). For each size category above Medium, double the creature’s carrying Capacity and the amount it can push, drag, or lift.
Four beasts of burden would be able to pull a carriage weighing 200 lbs. times their Strength score.
How heavy is the loaded carriage?
A normal carriage as per DMG already weighs 600 lbs. You say it will contain a driver and "important people", which sounds like more than one additional person. If we merely assume a weight of about 150 lbs per person with clothing, three people would already add 450 lbs, pushing the total to 1,050 lbs, over the target 1,000 lbs.
You describe your carriage as "ornate or armored" which likely would add another few 100 lbs, and that is before accounting for possible cargo. You might want to consider a larger pull target of something between 1,500 and 2,000 lbs, so that up to four passengers and cargo would fit comfortably.
Medium Sized Creature Options
If you are looking for beasts that have a real-world history to be trainable: Mastiffs are medium sized, are listed in the pack and riding animals section in the PHB, and have speed 40. Dogs have precendent pulling vehicles, for example sled dogs. Their overall height matches the 3 feet you ideally would like. By the rules, 4 of them would fit in the space of a large creature like a horse, and would be able to pull about 1,300 lbs at full speed.
Ponys and Mules also are only medium size, have speed 40, are pack and draft animals with even better strength than Mastiffs, listed in the PHB. In addition, Mules have the Beast of Burden feature, so they can pull twice as much. But they may be to tall for your taste? A small Pony would be about four feet shoulder. Four Ponies could pull a carriage of 1,500 lbs, four Mules could pull one of 2,800 lbs.
For more fantasy flavor, you could also use Boars, or domesticated pigs, or, as suggested by MivaScott, Goats, although by rules mechanics, they do not offer any advantages over Mastiffs (the goats are also weaker) and they lack the Beast of Burden of Mules. There is also no historical precedent of them being good draft animals.
Constructs: (If you like to stick strictly to prepublished materials, you can ignore this section.) Of course, if you are not limited to real-world animals, and if you already put magical guns into the top, you can easily also put a magical construct into the bottom to make this cart move, and make up its form and stats, or equip it with magical tank-like chain belts. Helmed Horrors are strong and only medium size, and you could reskin their stats for a four legged version. If all you care for is movement, remove their attacks and fly speed for higher speed (they only have 30).
Small Sized Creature Options
Small creatures technically need a 5x5 space just like medium creatures and therefore do not provide an advantage over them, unless you want to house-rule that more of them can fit in.
The options for this in the MM are rather slim. No natural beasts fit the bill. You could use fiends like the Dretch, Manes, or Spined Devil, magical constructs such as the Flying Sword or a monstrosity like the Darkmantle. Most of them are also pretty anaemic in strenght and could just pull about 1,000 lbs. (Darkmantle 1,600 lbs). Further, none of them would seem to satisfy the added requirement of being safe for common caravan drivers who likely would be scared by them.
Potentially you could employ Deep Gnomes, which have Strength 15 and are good aligned, four of them could pull a cart weighing 1,500 lbs. If you go down that route, you could also look to hire four extra-strong Halflings or Gnomes without the underdark weirdness.
