It doesn't have voice output (unless you connect it to a laptop) and has a small screen but the Garmin Etrex Legend C is (or at least was) the smallest GPS with a color screen that does autorouting. If you also want a handheld GPS for outdoors use (hunting or geocaching) this is a great little unit.

This spring I was in New Orleans on business with another techy who had a Dell Axion with a Bluetooth GPS receiver and we rented a Hertz with neverlost. The Dell did the fastest calculation of routing, the Neverlost had the best display and voice output and the Garmin gave the most detailed directions.

I have also used it on airplanes (be nice and ask the crew before you takeoff if it is OK). My current maximum speed is 586 MPH. Sure beats my BMW