Why does it have to be a 3.5" drive, exactly?
I'm using an ADSTech external 2.5" enclosure that runs firewire on my CarPC. It's currently hooked up and powered through the 6-pin firewire plug on my CarPC.
It works with a laptop too, and comes with a 6-pin to 4-pin wire to plug into the laptop, plus it powers the drive off a USB port. I think the case is (was, at least) around $100. Then just get any notebook drive you want. I know BestBuy sells a Seagate 100Gb for $200.
Or just find portable harddrives that run off USB..