Thankfully, it seems that a movement from inside governments is really starting, with more and more project funding demanding e.g. avoiding vendor lock-in. This helped push one of my projects from MSSQL to Postgres. One step at a time...
I'd envision building a plug-in replacement to facilitate switching.
But what really would rock the boat would be a MS 365 competitor, since that's currently suffocating everything, because everything is included: email, files, office suite, chat... None of these have to be the Same Product (and I'd prefer specialization), but the integration between different apps should be painless. So, protocols.
If nation states could onshore that package, it would even out the playing field for the other, more optional applications
From a public interest point of view I would say AWS, GCP and Azure
From the likelihood of a business being successful probably less well entrenched services, and ones politicians understand - so probably things directly used by consumers and very visible. Probably SaaS of some kind.
Also, its not just the EU (which is what the article is about). Non EU European countries, and the rest of the world too also have a problem with this dependence. I think the best approach would be broad collaborations on development, with deployment at a national level so every country could have sovereign data centres.
Going back to the old ways, where software was shrink wrapped, fast and local. So if that's where we end up I think we failed to make use of the potential in this forced decoupling event.
I would prefer that, but the GP was asking what a startup should try to do, and I think trying to get people to go back to using their own machines would be an additional barrier.
One could market strongly with the data privacy / sovereignty angle that resonates a lot more in Europe than the US.
I think its partly a cultural change with regard to privacy and partly learned helplessness.
As for services/products - cloud and MS. From MS - Active directory, Exchange, Outlook, Word, Excel and probably Powerpoint in no particular order. The key is not to have something basic cca working, we have those for decades and they are pretty fringe. Walking the last mile, the hardest part of smoothing integration, ironing UI, responsiveness. This would be a massive task, but worth it.
You have this, you don't need to look back at questionable US products anymore, at least not until they ship as bunch of code that you build and review locally. Goodbye NSA, back to cutting fiber optic cables on the bottom of the sea.
A lot of FOSS and other non-US software has at least as good UI and often better responsiveness.
However for many people particular apps they need are Windows only. Lots of industry vertical stuff.
With regard to marketing and branding, a lot of people use AWS because of the brand. Its not a particularly good provider of VPSs but I have lost count of how many people use AWS as a VPS provider (not using other services) and even worse most of them buy and instance plus storage rather than saving money by using Lightsail. I have had people argue that potential acquirers might be put off by using smaller providers.
In other words, if I were an EU startup, who should I compete with/try to clone?