Found out the issue thanks to a combination of “Rarst/laps” plugin suggested by @Punkwart and “Profiling and Logging in Query Monitor” that I mentioned in my initial post.
Rarst/laps plugin provided a very easy implementation of “light WordPress profiler” as the plugin documentation states. It helped me pinpoint the issue to “Template Loader” hook (template_redirect). Going to remember this one! Although I should definitely get Xdebug profiling to work as well in the future (when I make up the lost time… damn).
And I then used…
Profiling and Logging in Query Monitor custom profiling qm/start and qm/stop actions to see where the code is taking a significant amount of time to run:
// Start the 'foo' timer:
do_action( 'qm/start', 'foo' );
// Run some code
my_potentially_slow_function();
// Stop the 'foo' timer:
do_action( 'qm/stop', 'foo' );
Overall, big thanks to everyone who contributed to this thread and provided valuable information!