Ideally through hardware keys, but I see how that's hard to adopt. It's not entirely unrealistic though in the context of Play Store/App Store for the first download of an app from Google/Apple servers to be protected in transport by hardware keys.

Do the web browsers & operating systems face the same bootstrapping problem at the moment? At some point they must get their first certificate without using a certificate protected connection?

Edit - in the context of service which exists pre regulation, the client certificate could also be derived from the user's existing login credentials.