How much creative potential do you have? Are you limited to Excel types or could you extend it arbitrarily?
VBA is a kludge, but I've always thought that spreadsheets might be an interesting programming environment if you were restricted to the native functionality with a small addition. Namely, add a new value type: "anonymous function," which consists of parameters with an excel-native body, which can be assigned to a cell. You could then call the function by referring to the cell it's stored in (or any other way you can get a reference to it) and passing parameters. Function naming would work by using named ranges.