There's a great thread that just started over at Treocentral with a nice rundown on things people like to run.
http://discussion.treocentral.com/sh...d.php?t=159823
As for where you can get it, google the software names listed. You can also try googling "PPC freeware" for a few good freeware sites. The Treo is technically a PPC, so any of that sofware should run.
Just keep in mind that the Treo's screen (240x240) is smaller than most standard PPC's (320x240) so you can run into some snags there when the author doesn't build in autosizing or scrolling controls.
Oh, as for GPS, you'll need a GPS receiver. You can get a small BT connected one for not too much money. Google maps is free and will work with a GPS receiver to show location and directions.