So, I have been scratching my head about this for a day before I finally found the solution.
For some reason, after installing updates on my SP2013 machine, running the SharePoint Config Wizard kept failing at this point.
DB was up and responding, everything seemed fine, central admin worked, I could even access my sites with no problem.
Then I found some message in a forum that made me wonder, would it be because I deleted a web application before the updates?
The answer seems to be yes.
I used to have a SharePoint web application on http port 80 that had a dummy site that no one used.
It appears that once I deleted it - I started getting this error.
The solution was simple:
Visit the central administration, create a web application on default port 80, and create an empty site collection in its root.
Run the wizard again, and now this step passes with no errors.
Edit: while writing this post, I encountered another strange scenario which produced this same error:
The W3SVC service stopped, and stopped all sites with it.
Start the service and sites resolved this issue.