Usman Asar

it will be a double jump, from 3.1 to 3.5 and then to 3.9, you cannot straight away jump to 3.9.

3.5 being LTS, I would suggest holding on to 3.5 until December and then jump to 3.9, as still not every plug-in out there has support for 3.9, but developers are reaching there.

If you want to upgrade to 3.9, then look into your plug-ins first (additional ones) and make a list, then go into plug-ins directory and see if all are supporting moodle 3.9.

good thing on your hand, you don't have to worry about courses as since moodle 2.0 (I believe) courses backed up in moodle 2.x can be safely imported into any version of 3.x.

if everything's arranged properly, it's barely a 5 minute or less (assuming PHP and DB are upgraded already to support latest moodle)

That I am not sure how many concurrent users they have, even if we assume 15k, all wont be taking quizzes and quizzes are most resource demanding in moodle, you can always setup 2 DB servers with 3 web servers, and add on top if need be, as OU's hardware must be decade old, and architecture does effect performance. Rather than going to Linode, get AMD Epyc on NVMe drives. I am more into Windows server setups therefore wont be able  to assist much on Linux I am afraid.

CatalystIT have as well deployed a larger solution with 3+ million users for Saudi Government, they must have plenty concurrent to seek their assistance.

See if Tim Hunt can assist, they are running OU's servers with 10 web facing web servers and database on PostgreSQL with Master-Slave replication (not load balanced), if your client's user base is local, then ideally get servers locally as Linode will cost nearly $15k monthly.