There's plenty wrong with turn-by-turn navigation, so here's a completely different solution: boil the route down into the most simple set of rules possible — and leave the user to it.
There are plenty of systems that can be described far more simply than they initially appear — and directions are one of them. So instead of just describing which left and right to take based on distances travelled, an algorithm could boil down instructions to a simple set of logical rules which can be used to navigate to the same destination. If nothing else, it would keep you mentally alert during the journey. [XKCD]