AT&T 8525, Holux GPSlim 240 and TomTom PDA Software
I'm using this combo right now and it's the bee's knees. :up
The Holux GPS is about the size of a pack of gum and easily fits into a pocket. It takes about 1 minute of not moving and open sky to establish a signal but after that time it will work even in my glove compartment.
Google Maps and MS LiveSearch also work great but if you get out of a 3 G area then the maps are too slow to load to give you an effective system. TomTom ain't cheap but it works very well
Rumours are the 8925 is coming out soon with built-in GPS but it may be deactivated by AT&T so they can push their Telenav features.