Okay, figured this out.
The OS is Server 2016 Datacentre. Have rebuilt the servers several times, which includes the reinstall of WSFC feature and joining to domain. Looking at the logs folder, there's the cluster creation log which doesn't tell us anything helpful (just what I pasted in my OP). In the FcSrv.log, there's the following:
***** FcSrv Start ****
00001c8c.00001dbc::2021/03/22-04:54:32.266 RetrieveHostLabel completed with status = 0
00001c8c.00001dbc::2021/03/22-04:54:35.124 GenerateClusterCert completed with status = 0
00001c8c.00001dbc::2021/03/22-04:54:35.218 StoreClusterSecret completed with status = 0
00001c8c.00001dbc::2021/03/22-04:54:35.233 StoreClusterCert completed with status = 0
***** FcSrv Stop ****
***** FcSrv Start ****
000023b8.000023c4::2021/03/22-04:57:36.231 ENTER CleanUpEvictedNode
000023b8.000023d0::2021/03/22-04:57:36.231 ENTER EvictedNodeCleanupThreadProc
000023b8.000023d0::2021/03/22-04:57:36.231 ENTER CleanUpNode
Looks like the cluster service starts, waits for 3 minutes then stops again. Going through eventviewer showed a VERBOSE entry saying cluster service wasn't able to reach other node on 3343. Why that entry isn't shown as an error, and why that wasn't tested in the validation process, I have no idea. So opening up TCP 3343 in the security group fixed it (UDP 3343 was already open).