Unfortunately for you my friend, the gold-colored nature of gold is extremely dependent on the purity of the gold. Any and all alloys of gold will always not have the same lustre and color of gold.
Fortunately for you, gold is a metal, a pretty inert metal at that too. What this means is that your metal men can be made of whatever it is that you want, and you can then coat them with a very thin layer of gold. The gold can not be too thin however, otherwise you may have a problem with the appearance again, gold is fickle that way.
For your metal men to be be strong and powerful, you would then need to pick a metal. My personal favorite metallic element of all time would be Iridium, and in fact can be quite useful when combined with gold. Iridium can be used, when alloyed with platinum to make it much harder than before, up to 10x harder.
With an Iridium skeletal structure, gears and possibly muscle fiber, and a coat of gold paint, your metal men should be plenty able to hold themselves decently fine in combat. One thing that may happen a lot however would be that they would get a hillariously large ammount of chipped gold flakes whenever they strike or are struck. Actually that may be a pretty good combat mechanic for your metal men, as they fight, the air around becomes thick with gold chips, and that much heavy metal flying through the air can not be too good for the health of any meat bag enemies they face.
As for the Iridium in their bodies, they should pretty much reign supreme over any steel clad enemies, if their self-repair is sufficiently good. Iridium is a whole 2.5 points higher than steel on the Mohs Scale. As such, any cutting or thrusting attack on them with steel weapons will fail, as the steel is not hard enough. However, hardness comes with the price of brittleness. If a giant were to swing a giant steel zweihander at your Iridium core metal men, the giant's zweihander is liable to get blunt, but your metal men may risk getting blown apart. But they can pull themselves together, so they will be fine.
With that much Iridium and gold on the metal men, they would be incredibly heavy. Over 1.5 tons per metal man. With that kind of weight, they would pose an extreme weight hazard. A squad of a dozen metal men could easily collapse most simple bridges. It would not be too much of a stretch as well to say that they can easily launch themselves from very powerful siege engines directly into the enemy wall, causing huge damage to the wall, as the metal man is many times heavier than a rock, and several times smaller as well, which may allow a flung metal man to be capable of punching through the curtain wall of a castle.
Their immense weight and density can also help them be innately hammer-proof without the need for any sort of special armor. In fact, the metal men would probably not need any armor or weapons. They could easily sharpen their arms into blades and charge into battle arm flailing. No weapon of steel would be able to deal with them easily, and their flailing blade arms would actually be capable of chopping through enemy weapons and armor. One thing to note is that they weigh 1.6 tons, and a human arm is roughly 1/6 the total body weight, so that would be a 260kg blade arm swinging about.
I would also like to note that I am assuming that they are powered by magic, and blessed by magic to be able to move their bodies exactly as fast as a human could, but they are 1.6 tons.
NOTE 1: Why is Iridium so heavy? Because it is in the Platinum family of elements, which go from silver -> gold -> platinum -> iridium, with each later stage being quite a bit more dense the one before.
NOTE 2: A fallen metal man would be worth USD 28,270,000. Considerably beyond a million dollar man
