Question: Having a brick lying on a table, I can exert horizontal force equal to $\mu m g$ to a middle of it's side, and it will start moving (assume $\mu$ is the friction coefficient). However, can I make the brick moving with less horizontal force? May be, applying it not to a middle of a side can help? I have no idea of how to calculate or estimate it, but it would be interesting to know.

Answer: 
This may be a bit of an eye-rolly answer, but since you specifically state that all you care about is minimizing the horizontal force:

All you need to do is lower the normal force since the horizontal force you need to apply to get the brick moving needs to overcome the force of friction. Since friction, in the static case, is the coefficient of static friction times the normal force - and assuming that you can't change the interface between the surface and brick and therefore can't change the coefficient of static frction - lowering the normal force lowers the amount of horizontal force you need to apply. 

Therefore, apply a vertical force to the brick to lower the normal force and - ZOOM - you're off to the races! Ahem. You know what I mean...
If you can't change the brick or the surface(or the contact eg by lifting the brick)  

Then how you put the force into the brick doesn't change the energy treansferred