Hcfyk

A set of large mainsprings.

The springs could be 'charged' like modern batteries by winding them up and may be exchangeable in a modular fashion.

Springs tend to be large though, especially when all the 'charge' has been used up, so I doubt this is a very good solution.

Though the engineering would have been tricky, consider the possibility of a tiny steam engine driven by the decomposition of hydrogen peroxide, a chemical certainly known to Victorians. Highly concentrated peroxide can be flowed over a suitable catalyst (eg. a silver wire) and it decomposes quite energetically into steam and oxygen. Manufacture of suitably robust and long-lived seals for such a system is left as an exercise for the reader.

Leaks of high-test peroxide are potentially quite hazardous as it can rapidly ignite all sorts of stuff and can be quite toxic to humans. I'm not sure of the minimum concentration required for this technology to work, and so I can't tell you exactly how dangerous it might be, but it won't be quite idiot-proof.

The idea has two interesting knock-on effects:

Firstly, it provides a justification for the endlessly reused victorian steampunk trope. You may or may not consider this to be a good thing.

Secondly, it might bring forwards the discovery of liquid rockets by decades, which will have quite an interesting effect your future history ofthe 20th century; not just in warfare but in the progression of technologies for flight.

For reference, the estimated energy density of a mainspring is 1.5KJ/l (from this physics.se answer). 60% peroxide is more like 3MJ/l, so that would give you a ballpark figure for how much better the little steam engine could be (not taking into account all the possible inefficiencies, which will be legion, but it'll still come out ahead) For comparison, petrol (or gasoline, if you prefer) is over 34MJ/l, and lead acid batteries are around 0.5.

Gravity

Your automata have a mechanism that translates gravitational pull into e.g. the rotation of gears, just like the pendulum mechanism in a traditional cuckoo clock, which uses wheights hanging on a cord or chain as power source (the actual power is produced by a crank, not by the pendulum).

That requires such chains hanging from the body of the automaton, but I'm sure your people could integrate them into the general aesthetics as leashes or decorative bands.

The bigger problem is that you either need several such mechanisms to create enough energy, or the wheight needs to descend rather quickly to spin the gears faster (which can be translated into more force). Someone needs to "wind them up" (or rather pull the chain so the wheight is lifted higher again) before their wheights reach the floor and all the gears simply stop spinning.

Hot radioactive elements driving an ether engine.

The ether engine was a real thing in the mid1800s; this among other engines working on the principle of the steam engine but using working fluids with a lower boiling point than that of water.

I propose your automatons have onboard ether engines heated by a lump of a radioactive element - actinium could work, or thorium, radium, even compressed radon. Many of these radioactive elements were discovered in the late 1800s and using radioactive things this way smells steampunky to me. On being purified, many of these emit heat via radioactive decay. Purified actinium can get hot enough to melt itself. Automaton (cancerproof) mill workers would make the purification of these elements safer.

Different automaton makers could have their own proprietary engines (actinium and ether, radium and chloroform, ultimum and benzene, etc.). Each touts the merits of its own system and the dangers of the others. I can imagine home users not wanting to purchase radionuclide fuel and hacking their automatons to run on thermite, or supersaturated sodium acetate.

Flywheels

Flywheels have been used as 'batteries' for electric buses in the past and are used in kinetic energy recovery systems for race cars as well as grid level energy today. Today we can achieve 0.5 MJ/kg with carbon fiber composite flywheels operating in a vacuum at 60,000 RPM with magnetic levitation bearings. One big advantage of flywheel systems is that they can be recharged fairly quickly. Very fast discharge is possible too.

Flywheel energy density is roughly proportional to the strength to weight ratio of the materials we make our flywheel from and is given by Energy Density= K*MaxStress/density. K is the shape factor which describes how efficiently we use the material in our fly wheel to store energy and ranges from 0-1, with 0.5 being pretty reasonable. Max stress is the maximum amount of stress our material can take, and density is density of the flywheel material, for energy density in J/kg use pascals for stress, and kg/m^3 for density.

So let's figure out what the energy density could be assuming we don't have carbon fiber. Assuming maraging steel with a yield stress of 2400 MPa and a safety factor of 1.3(max stress ~1800 MPa), with a shape factor of 0.5, we get an energy density of 0.11 MJ/kg. This is somewhat reasonable given that lead acid batteries have an energy density of around 0.14 MJ/kg.

However, both these energy density numbers come with an asterisk. For long energy storage we must put our flywheel inside a vacuum chamber to eliminate air drag which adds weight. The bigger issue is that flywheel energy storage becomes a very efficient bomb should the flywheel fail, much of the stored energy will be converted more or less directly to flying shrapnel. So we need to armor our flywheel. Another disadvantage is that energy slowly drains due to bearing friction. This can be quite low if we use magnetic levitation bearings, but I don't think a steam punk world will have this. For maximum energy density, we should spin our fly wheel as fast as possible, but this creates more wear and tear.

A cheat to make flywheels work is to suppose we have access to a high strength to weight ratio material which I am going to call unobtainium. We can suppose that the strength to weight ratio for unobtainium is ridiculously high meaning that our flywheel system doesn't need much of it. Perhaps we only need a vanishingly small amount like milligrams or less for practical energy storage. This means we can limit the damage a nigh indestructible material like unobtainium does by making it ridiculously expensive and only practical for flywheel energy storage.

Heat Engines

Since you specified that "fine mechanics is advanced and reliable enough to replicate integrated circuitry," it should be possible to make fairly compact heat engines capable of burning hydrocarbon fuels. As an example of how we can take this to the extreme, very small gas turbine engines have been proposed as a replacement for batteries.

While the above have used the brayton cycle, which is the same thermodynamic cycle used by jet engines, we can also use the rankine cycle, which is thermodynamic cycle any power plant with a steam turbine uses. It has been proposed that one could make a steam turbine powerplant on a chip with ~11% efficiency and a power density up to 12 KW/kg. This is comparable in power density to a GE90-115B Brayton turbofan jet engine at 10 KW/kg.

It's also been proposed that one could use tiny organic rankine cycle turbogenerators with solar concentrators as a replacement for silicon solar panels in satellites. Now what really enables us to make compact rankine cycle power plants is being able to make relatively compact boilers and condensers. If we can make complicated tiny mechanisms we can probably make a complicated arrangements of tiny pipes.

Hydraulics or Pneumatics.

Even today, much of our electrical machinery trails a wire to the nearest power socket. Until a decade or two ago, batteries were far too big and heavy to provide a viable alternative.

Back before electrical utility power, utility hydraulic power was a thing. The London Hydraulic Company installed strong cast iron pipes and had coal-fired pumping stations to pressurize water in them to far higher pressures than water supply. (The pipes still existed long after the system ceased operation, and now contain fiber-optical communication cables). Hydraulic mechanisms are still used, for example in earth-moving machinery, but are now locally powered from an internal combustion engine, or via an electric pump.

Compressed air is also still used, again generated locally. Pneumatic mechanisms are less powerful but can easily switch on and off in tenths of a second, and less easily in milliseconds.

So your automata could run off supply and drain hoses plugged in to high-pressure water, or a supply pipe plugged into high-pressure air(*), either generated by a large steam engine at a distance of anything up to a few kilometers. Had we been only a few decades later developing electricity, I suspect most towns would have gained a hydraulic power utility.

(*) return pipe optional for air, but it might keep the noise level down.

PS it has always piqued my imagination that had Babbage ever met a person who knew about pneumatics, it's possible that he could have built a binary pneumatic computer working at somewhere between 10Hz and 1Khz in his lifetime. The course of history would then have been utterly different!