I have had Navfree for ages and it more than does the job for me, stick a headphone in while riding and get directions more than early enough to take the exit.

Haven't tried Scrobbler but used to get Navigon for free and that was pathetic, you downloaded an 800MB map update and it still required 3G enabled to work. No way I would advise anyway to pay for it.