The minimum device for running Palantir runs Palm OS 3.0, has an IrDA port, and has available memory to store your music database. Almost all Palm devices have 2 megs of memory, so that should be enough for you. My database is ~420k and I have about 5800 songs, so the rule of thumb is probably: if you have more than 10k songs on your player, get a Palm device with more than 2 megs. Devices that meet these minimum criteria are the Palm III series, the Handspring Visor series, the Zire, etc. I think that they made some Palm IIIs without IrDA, so just make sure it has an IrDA port before buying. Basically, every Palm unit except the original Pilot series will work with Palantir. You can buy many of these lower end units (especially Visors) on eBay for around $40.

There is no recommended unit as long as you can store your database on the unit. The minimum requirement units work just as well as a brand new Tungsten C at running Palantir, so you should be asking yourself "what else will I be using the Palm device for" and then buy using that criteria. If you are going to be using it only for Palantir, and keeping it in the car (you might as well sync phone numbers and addresses to it too), you should probably buy a Handspring Visor on eBay for cheap. If you want to use the device for other things (phone, color pictures, portable MP3 player) there are many, many other choices out there that would be best researched on another website. A few that are pretty good:

http://www.the-gadgeteer.com/
http://www.palminfocenter.com/
http://www.epinions.com