I would say most people use the terms interchangeably. Power, in this case, is the same as electricity. In technical terms, power is the ability to do something whereas electricity is a form of energy. In daily speech, most native people understand the term no matter which one you use. In fact "electric power" is often used too. After all, electricity unused is in reality just power waiting to be applied.

In your example, both are correct. However, "electricity" refers only to 电力, whereas, "power" can include 力 (功率, 动力, 权力) more broadly. But if my lights stop working during a storm, I can say either "Oh no, we lost power" or "Oh no, we lost electricity" and the meaning is the same. Same with "electric company" and "power company."

Electricty is just one form of energy. Power is a rate of producing or using energy. The gas company is also a power company. But most people would probably say "gas company" and use "power company" only for the electricity company. Hence the good answers below. I guess I'd be more inclined to say "electricity company" than "electric company", but maybe that not universal over the globe.