Compressing air from atmospheric pressure into high pressure storage and expanding the compressed air in reverse is a means of energy storage and regeneration for fluid power systems that can potentially improve energy density by an order of magnitude over existing accumulators. This approach, known as the "open accumulator" energy storage concept, as well as other applications such as compressed air powered cars, rely on the availability of efficient and power-dense air motor/compressors. Increasing power is typically accompanied by reducing efficiency with the trade-off being determined by the heat transfer capability. In this paper, the authors present the Pareto optimal trade-off between the efficiency and power for a given heat transfer capability and ambient temperature in an air motor/compressor to achieve a given pressure ratio. It is shown that the optimal frontier is generated by an air motor/compressor that compresses and expands the air via a sequence of adiabatic, isothermal, and adiabatic processes. For the same efficiency of 80%, such an optimal volume trajectory achieves 3-5 times increased power over ad-hoc volume trajectories. It is also shown that approximating the infinitely fast adiabatic portions by finite time processes do not significantly reduce the effectiveness of the optimal operating strategy.