Why are "ice cube" PCB mount power relays pinned out so that the COM pin is between the coil pins?
It's only to make the relay cheap. It's sub-optimal internally (electrically) as well as externally (pinout). The coil-to-contact breakdown voltage and capacitance is inferior to that of better relays. On the other hand it's cheap and the relay can be made reasonably sensitive (360mW typically for that construction). 

One of the disadvantages of this construction is that the contact current always flows through the flexure, so a large surge (say to blow a fuse or circuit breaker) can anneal the spring and affect the operation permanently. 

Below are a couple of photos of one I did a tear-down analysis on a few years back. 





The common pin is naturally located at the other end from the contacts. They could have moved the coil pins to the front or back but either way they are close to the contact potentials unless the relay is made wider.