I rented a Hertz car with Never Lost when I was in Denver, CO. on business. Loved it.
I don't know where you can rent a car gps in Canada but...
I just upgraded my gps to a Garmin gpsmap cs60 and loaded it with maps from Mapsource MetroGuide Canada. The auto-routing is very much like NeverLost but without the voice commands. Just for fun, I connected my gps to my laptop and ran nroute which you can get from Garmin. That combo provides a great visual of the route and turns and provides the voice commands that I enjoyed from NeverLost. And the large display on the laptop gives you much more information.
The laptop, nroute and Mapsource MetroGuide Canada and my old gps (Garmin etrex vista) works too.
It's not NeverLost but these are tools I use anyway for geocaching so it is free.
And don't be concerned about Ottawa street detail, it is all there.
Hope this helps.
Nawty aka Renate