Sometimes that's through new paradigms, but more often that's through incremental evolution.
Have a great idea for a spreadsheet? To implement it competitively you'll spend 99% of your time reinventing Excel and 1% of your time on your great idea. Or you can add it to gnumeric.
More likely you'll release an Excel plug-in, but what do you do if Excel doesn't have the right API hooks?
Adding more is only one way to innovate. You can also innovate by changing things or by taking things away, thus bringing what remains into sharper focus.
A car does not do everything a horse can do and more, but cars still made horses obsolete for transportation. Cars can't jump over obstacles or reproduce, but apparently these features weren't really that important.
An iPad can't even compile Hello World in C, but apparently that isn't that important to a lot of people.
Nick Cernis innovated in the "to-do" space not by doing everything other to-do systems could do but by replacing software with a pencil-and-paper system that serves some people better (see: http://todoodlist.com/).
A spreadsheet is a means to an ends. If you have a great idea for a spreadsheet, what you really have is a great idea for something people need a better way to do that you think could be implemented in a spreadsheet. Instead of reinventing Excel, you might come up with an alternate way to get to the same end.
The point is that innovation comes in many forms.
You're reducing a complex problem too far.
The word you're looking for is "one".
If one wants to get converts, one should make the software that makes today's software obsolete. If one doesn't make it, someone else will, and when they do, one's FOSS version will be obsolete as well.