How expensive are Hartree Fock calculations?
I wouldn't call the Hartree-Fock methods 'very simple', I would consider it fairly complex both in terms of its derivation, interpretation, computational cost and implementation details. If Hartree-Fock calculations are now commonplace it is also because so many man-hours of study have been devoted to it. 

In any case, as you say, its formal cost is $n^4$ ($n=$ number of basis functions): the number of two-electron integrals is $n^4$, and all these integral are necessary to build the Fock matrix, so the overall cost is also $n^4$. However, this is not the end of the story; as a system grows larger and larger in spatial extension many of the required integrals become vanishingly small and can be neglected, and other approximations become possible, at the cost of introducing a small and adjustable error. As long as the error introduced is (much) smaller than the intrinsic error of the Hartree-Fock method, it doesn't really matter. Some keyword often used in this context are 'linear-scaling' and 'density-fitted' methods. 

The difficult, computationally expensive part of the Hartree-Fock method is dealing with the electron-exchange part of the Fock matrix, and most studies try to speed up this step. For example, a recent study of this type is:
Christoph Köppl and Hans-Joachim Werner, Parallel and Low-Order Scaling Implementation of Hartree−Fock Exchange Using Local Density Fitting, J. Chem. Theory Comput. 12, 3122−3134 (2016).

In this study the largest calculation they report on is for alpha-cyclodextrin, a polysaccharide with formula $\ce{C36H60O30}$ (126 atoms, 516 electrons); using the aug-cc-pVDZ basis set (2058 basis functions) the authors report that a density-fitted Hartree-Fock calculation took about 4 minutes on a beefy workstation with 20 cores (two Intel Xeon E5-2690 @ 2.8 GHz).