The "best" anything always depends on what you want to do with it, and how important cost is. The most popular car applications (mp3, gps, etc) can be done with fairly little processing power, but who knows, maybe you want your back seat passenger to be able to play Doom3.
Between your 2 CPUs, I'd just stick to the P4 precisely because you already have the mobo. You can underclock it if you think heat might be a problem.
A desktop PSU will work, but you'll need an inverter. A more elegent solution is a DC-DC power supply, but these can get fairly pricey. You can find just about every possible solution in the Power Supplies forum, so go check them out.
Your best bet for used laptop HDs is probably ebay. Maybe others know a good source? Laptop drives are less likely to suffer damage in a car, since they are built with being moved while operating in mind, work at lower speeds, and have lighter heads. Still, many people use desktop drives without problem.
Hope that helped.