After patching the passive node and rebooting it, we've tried to failover to that node. But surprisingly it took ~ 10 minutes to start the SQL Server service which hanged on change pending state.
After patching, as you've astutely stated, upgrade scripts still need to run against every database. Currently, there are 500 databases on a server with 16 cores, which results in a value of 704 for max worker threads. While I don't necessarily believe you're hitting a MWT issue (though the errorlog would tell you and we don't have the errorlog) I do believe you're having a combination of too much work on too little of a system. It's not enough to bring the system down or crash anything but enough to make it take time to finish processing items. This is also a VM, we have no idea about the host or what it may or may not be doing in terms of resource fairness.
This downtime period seems to me very long, just searching for ways to decrease it somehow. If you have any suggestions, I'll be more than happy to listen to them.
Since I don't have a copy of the errorlogs or performance counters, it's hard to be exact or accurate, so the above is based off the data we currently have. Any number of other factors can be involved here, including disk access times, other items on the server, available and max server memory, etc.
There's no single knob or item, unless you have data that shows X was slow or Y took a long time - then you can hone in on that. Currently it does seem as though you have many databases on the system for the number of CPUs available.
If you have a similar setup test system, you can setup performance captures and run the patching process -> failover, to get more information.
From the comments:
Unless it's changed since 2016 (and AFAIK it hasn't), the upgrade scripts run through the databases serially (so MWT won't come into play) [...]
This is not correct, at least since 2005 it's not worked that way. Databases will be started in parallel and upgrade as shown below which is an excerpt from a CU update I ran after creating 500 dummy databases.
2023-04-25 05:44:27.98 spid20s Starting up database 'BreakMeDB1'.
2023-04-25 05:44:27.98 spid21s Starting up database 'BreakMeDB2'.
2023-04-25 05:44:27.98 spid22s Starting up database 'BreakMeDB3'.
2023-04-25 05:44:27.99 spid31s Starting up database 'BreakMeDB12'.
2023-04-25 05:44:27.99 spid33s Starting up database 'BreakMeDB14'.
2023-04-25 05:44:27.99 spid32s Starting up database 'BreakMeDB13'.
2023-04-25 05:44:27.99 spid27s Starting up database 'BreakMeDB8'.
2023-04-25 05:44:27.99 spid29s Starting up database 'BreakMeDB10'.
2023-04-25 05:44:27.99 spid34s Starting up database 'BreakMeDB15'.
2023-04-25 05:44:27.99 spid28s Starting up database 'BreakMeDB9'.
2023-04-25 05:44:27.99 spid23s Starting up database 'BreakMeDB4'.
2023-04-25 05:44:27.99 spid24s Starting up database 'BreakMeDB5'.
2023-04-25 05:44:27.99 spid30s Starting up database 'BreakMeDB11'.
2023-04-25 05:44:27.99 spid25s Starting up database 'BreakMeDB6'.
2023-04-25 05:44:27.99 spid26s Starting up database 'BreakMeDB7'.