Garmin etrex (more designed for hiking but useful for anything) will let you follow pre-planned routes and navigate to places ad-hoc but it's not as nice as Edge models for use while cycling.
Thanks all - some interesting options.
Still can't believe no one's just made a sat-nav for bikes without fucking around with performance stats or compulsory scenic routes. I shall just have to invent one myself!
Phone shop, here I come (if I can find it on my huge paper map, etc etc)
So, before I go and get a new phone (I have a brick).... is there not a cycle-specific gizmo that does this too?