If you don't mind an external GPS reciever, then any PDA with Bluetooth should do the trick - you can get a BT GPS off eBay for ~$50 with shipping (Holux M1000). There are some devices that include the GPS, but I can't remember model numbers off the top of my head.

Then, you need to buy mapping software like TomTom for the PDA.

If you go with a Windows Mobile based device and have a live data connection, you can either use Live Search (wls.live.com) or Google Maps to provide rudimentary navigation for free, but again, you have to have a data connection to download maps on the fly. I've got a Blackjack (personal) and Treo 750 (work) and that's my method. GPRS/EDGE data is fast enough to do the maps unless you're fully-zoomed in on an interstate - then the tiles don't always refresh fast enough.

The advantage of the external GPS is that it can be used with other devices if the circumstances warrant - I could use my BT GPS with MS Streets and Trips on my laptop if I wanted, too.