Analogies like "painting a room" are pretty useless because they are very misleading. Especially when it is an innovative product, a better analogy would be: "painting a room on Mars". With software development, there are a lot more "unknown attributes" that determine the main part of the effort estimation unless it is a repetitive task. So, a critical/skeptical engineer would always drive the customer nuts by asking…
The most common kind of software projects I've encountered are very straightforward, mostly just CRUD with an interface + business logic, and reporting, or relatively straightforward websites. Those are the "paint the room" type of projects.
There are challenges with those kinds of projects, but they should be reasonably easy to estimate, as long as the team is somewhat familiar with their development tools.
Other kinds of projects ARE more difficult because they have unique or innovative elements (probably the case for a lot of startups). Those might be the "paint a room on Mars" kind of projects.
As an employee, I've encountered the first kind 90% of the time. As a startup founder, I have encountered a lot more unknowns, but I've still found my project reasonable to estimate.