Anyways.. Not too sure whether you should go to 2 devices or stay with 1, as I guess that depends on the support or accessories you can get your hands on with a PDA, but there are tons and tons of add-ons that you can get for an Ipod, now Im not saying Ipod is the way to go or not... I have one, they work great and sound fantastic, with the right set of headphones, or earbuds.
I like the Nano and 2 gigs is a decent amount of storage.. I have 4gig.
How many songs depends.. but its still a cr@pload.. Many hours..
FM transmitters for in the car hookup, docking stations for your home..
If you do decide on an Ipod, don't use that PIA Itunes software.. It sucks...
Mediamonkey or
http://www.redchairsoftware.com/anapod/ works good, and there are a couple of others as well...
Downloading music, you can use torrents sites, but make sure you are not sharing what your grabbing...
Good luck...