Flickering lights when appliances turn on
I agree that it is a good idea to start with the power company in this matter.  

Places I have seen this problem start from is higher resistance connections for the mains in the panel box, and higher resistance connections in the meter box, on the mains.

Most of the time, in my limited experience, it has been the mains into the power box.  You will want electrical gloves and appropriate tools.

Some of the time it is connections in the meter box.  Most frequently the fingers which grip contacts on the meter.

If you are not comfortable hunting this down, I suggest getting someone who is and has the right tools.  But if you power company investigates first, you will at least have assurance that the power available to you is stable.