Delorme's XMap Handheld isn't bad. It requires interaction with a desktop system to get the maps installed; but it does handle some basic routing on the handheld. I've got an older Clie (T615C) so it's pretty slow on my device, but still usable for the little stuff. When combined with the desktop app, you can create both the maps, and the route info (turn-by-turn directions) and send them to the handheld for use away from the computer. Not feasible to load the entire US map onto your handheld, so you need to prep for where you'll be going.
They don't have a demo available. But some useful info at their website (
http://www.delorme.com)
On my older Palm IIIx I used to use Rand McNally's Streetfinder; but it didn't support route creation on the handheld. Everything had to be prepped on the desktop and exported to the handheld. It worked great with their Palm GPS unit, but if you needed something you hadn't planned prior to leaving, there was no on-the-fly route creation. There's anewer version out, I believe, but I haven't looked at it.
Hope this has been somewhat helpful,
Scott