First of all, kudos for wanting to do that - as others pointed out, optimization knowledge is vastly underutilized throughout the industry and we need more people like you. People have already given some excellent answers, so I'll focus more on the company-building point of view.
As you realised, the most important thing is to identify the problem you want to solve - the solution will come later, once you have identified something that people care enough about to actually pay money for.
The second most important thing is to identify your market. Selling to consumers is very different than selling to companies: companies have long sales cycles, you need sales people and account managers, you need to do demos, charge a lot more money because you have fewer clients, provide stellar support, etc. Consumers on the other hand will simply buy your product if they like it and the price is good, but you need to raise awareness and build up the consumer base.
Application-wise, where to even begin? Interfacing existing applications, creating specialised solutions for sectors that don't traditionally use optimisation, creating tools to improve the workflow, tools to make modelling easier/more accessible, tools to process data before people even start optimising. Funnily enough, solvers are the toughest market because it takes so long to develop a solver that works properly and efficiently.
Overall, the greatest advise I can give you is to talk to people. What we think the community needs is rarely what the community actually needs. A great book on how to interview people for information is called The Mom Test.
As you mentioned, coming up with a demo, (or Minimal Viable Product) is tough in optimisation. We faced this problem a lot when building Octeract Engine - you don't just build a demo for a high performance solver, it either works or it doesn't. What we did instead was to make sure that the product, if and when it would be ready, would actually be useful enough for people to buy it, and we did that by interviewing people about the challenges they face and by crunching market data. Once we had that information, we then invested resources, effort, and time to build the engine, but not before.
Finally, whatever you end up choosing, make sure it's something you will enjoy doing and that you are passionate about. Building companies from scratch is hard, so you might as well have fun doing it.