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'd keep you mentally alert during the journey. [XKCD]