What you are refering to is a handheld computer with integrated GPS or one that connects wirelessly via Bluetooth to a seperate GPS receiver. I started with a Mio 168 Pocket PC in 2005 and recently got an old Dell Axim x51v to replace it. On both of those I have TomTom v7 which is now out of date, however the maps are still being released on a regular basis for the v7 app. The modern successor to the Pocket PC are devices like the iPhone or HTC range.
It's up to you what you buy, but despite the Dell being oldish I got that to last me another few years until the Android based PDA devices mature, plus TomTom are working on an Android version. Also there is a massive range of GPS programs that you can install on a Pocket PC or HTC, including for walking or any kind of travel for that matter even sports and fitness. My Dell was £40 from Ebay and came with the seperate GPS receiver and many other extras.