Well, when exactly do you consider the page to be “starting to load”?
get_header() is typically the first function to fire as the html of a theme is starting to generated. It fires the get_header action. Numerous hooks fire prior to that, at different points, the very earliest being muplugins_loaded I believe.
wp_loaded, by the way, is not when the page has fully loaded but only after WordPress has loaded. There is a difference. A number of things happen before the page is created and sent to the browser.