I run Garmin mobile XT on my HTC Touch HD and it's excellent. Had Tomtom on a Palm Treo before and that was good too (but let down by the screen size).
If you get/have a dedicated touch screen phone with a decent sized screen then it is well worth it in my opinion. You then also have the added benefit of live traffic updates and other web based things (Google search for directions to any directory location is good too).
I would never go back to a dedicated unit. Surely that is one of the biggest benefits of a 'smart' phone – it has loads of uses so you don't have to carry half a dozen electronic devices around with you!