What temperature should eggs be when I beat them?
Assuming you're talking about beating egg whites, the best results are obtained with fresh, cold eggs (as you noticed).

Warmer (or older) eggs will gain volume quicker, but the resulting foam will be less stable. Since nowadays everybody will likely beat the eggs using some form of mechanical mixer, the time factor is now irrelevant, while the foam stability appreciated.

The "baking rule" probably originated when refrigeration and mixers weren't around.

Here's a list of things influencing max volume and stability:

Age: as eggs age, their pH increases: around 7.6 when laid, 9.2 after just three days. Lower pH is better for stability.

Temperature: temperature at the time of beating does not really make a difference, but if you refrigerate the eggs you'll delay protein denaturation, increasing stability. Heating the white to 58 °C for three minutes increases the foam formation ability, but over that protein denaturation will ruin everything.

pH: adding a bit of acid (citric, tartaric) will help both volume and stability. Citric acid can also help with keeping the foam white.

Water: adding water (up to 40% of weight) will yield a less dense, slightly less stable foam

Sugar: adding it will slow foam formation, and yield a denser, stabler foam.

Yolks and fats: Avoid. A single drop of yolk can reduce the final volume by two thirds.

Copper bowl: lengthens the time needed, but will yield a stabler foam.

Salt: shortens the time need, but will yield a less stable foam and increases syneresis (weeping).

On a side note, there also is a myth that older eggs are much better for macarons, but it has been debunked.