If you want a free one that uses data to get directions: Waze
If you want one that has on-board maps and doesn't need data: Navigon
Navigon + AroundMe is a perfect combo.
Subjective matter. Don't assume that your preferences/situation are universal.On board maps isn't an issue as you can pre-fetch maps before you leave on a trip if you think you might hit dead space.