Amazon's main strength is warehouses and fullfilment. Flexe, through a new, low capital biz model, similar to airbnb, have created a large fullfilment network across the US. There's potential there, maybe to hurt Amazon. Also, this will be expanded globally, and hurt Amazon further. it's just a question of when, i think. Altough , on the other hand, Amazon's seller-fullfiled-prime may be a good antidote.
Also wish.com(cheap good directly from china,maybe opening a US warehouse) does interesting things in trading quality/speed for low price, and there might be a path for them to retain low prices while improving quality/speed.
Startups that will help Walmart to challenge Amazon, could also be a great help. so there's that startup that made a robotic parcel locker , much bigger with higher package density. or any new tech that can help walmart with their giant parcel lockers for groceries(including chilling , etc).
For instance, the more specialized a text analysis system is the more tractable the problem of getting it "good enough" for commercial use is. Company X needs something trainable for company X's universe and will find that training for other things will at best cost money they don't have, at worst, distract from good performance on the X universe.
Much of the "AdTech" biz centered in NYC is there because Google has never wanted to play the high-touch sales game in advertising.
However, they are being challenged by groups of smaller startups.
For example, Facebook is losing its appeal due to apps like Snapchat, Houseparty, etc.
Amazon is being nibbled away by direct-to-consumer companies, like Casper and Dollar Shave Club.
Google is getting challenged by voice assistants, chatbots, and so on.
A good way to think of it is not as who can challenge these companies, but which human needs can be served better.
Could a startup challenge one of these companies individually? Yes. All three at once? No.
But I don't see why there couldn't be a search, social, and shopping startup. Success is not necessarily taking dominant market share.
Previous tech history suggests that the big ones (like WordPerfect) go down when they stumble or just ossify and refuse to improve for a long time.