I have thought about this myself too, so I'll offer my two cents: Spreadsheets are really versatile, but they're a victim of their own versatility. You need to build something that is similar enough that people understand the concepts, but different enough so that people don't get frustrated by the fact that it's not Excel/Google Docs.
I always envisioned something that functioned like a Jupyter notebook, and pulled some pages from the MatLab debugger tool ...kind of like how Light Table implemented them, but don't get too caught up in that analogy. That way, you could create and define tables that are stand alone objects, and run [code] operations on data in those objects to create new tables. Everything that is processed from the tables is it's own [new object] entity, and can be [output or not] viewed or hidden. It would move away from the idea of having few tabs of large continuous spreadsheets in favor of having many small tables [matrices] that would have identifiers [variable names]. And if the user really wanted, they could drag around tables on a spreadsheet like grid, but the data in those tables would not be editable in that view. Oh, and graphs are their own entity too. Users can use a GUI editor to make graphs, but the graph properties will be user accessible in some sort of markup language for the edge case where the user needs to make a ton of graphs, and then needs to make some styling change to every graph. Not something I've ever experienced though... \s
This will:
1. Reduce the need for Excel's reference gymnastics that are performed when you move or insert rows/columns in to referenced data.
2. reduce the headache that is excel formulas. Since each object will be a formula instead of every cell. Also, the formulas don't have to be a single line, so it will be more readable.
The trick is finding a good language to use - Julia maybe? and designing a good GUI for helping non programmers do useful things like accessing and referencing data from objects in an intuitive way. This could be where the traditional spreadsheet view could come in handy. I like how you mentioned that it needs to serve as a good on ramp for ever growing programming skills, because it needs to be intuitive enough that non programmers can understand the basics and accomplish something useful, but powerful and hackable enough that the mental models can transfer.