The only real complex problem a start-up has to solve is making the product successful. Engineers that love "complex problems" with no love for the product / space it's in is usually a recipe for disaster.

I think it's completely reasonable for a CEO to have a different view, and when you're a tiny startup, it's very fair.

You can be, but I wouldn't hire that person. Why would I want an engineer who doesn't give a shit about the actual product they're responsible for?