Well, no real progress has been made in parallel programming in the decades of research (apart from the embarrassingly parallelizable), so we're probably going to have to give up something in our concept of the problem.
But I really like determinism. If the proposal works out, future computer geeks will have a very different cognitive style.
Another approach might be to recast every problem as finding a solution in a search-space - and then have as many cores as you like trying out solutions. Ideally, a search-space enables some hill-climbing (i.e. if you hit on a good solution, there's a greater than average probability that other good solutions will be nearby), and for this, it is very helpful to know the result of previous searches and thus sequential computation is ideal. But, if the hills aren't that great as predictors, and if you do feed-in other results as they become available, the many-cores would easily overcome this inefficiency.
An appealing thing about a search-space approach is that it may lend itself to mathematically described problems, i.e. declare the qualities that a solution must have, rather than how to compute it.