I'm running a Dell Latitude CPI (PII/300) with Debian 4.0 (Etch) that I just got installed. My boot time is on the order of 2 minutes, with no tweaking for efficiency yet. I'm thinking of using some sort of hibernation to reduce that to as little as possible.
I did think of a kludge ... get a cheap 128mb/256mb MP3 player, and wire it up to start playing at power on, then the car computer can take as long as it wants to start up, que up a new mp3 to play, and wait for the MP3 player to reach the end of the song, and then play (monitor the sound-out of the player for silence). After that it can erase the MP3 on the player, upload a new one for the next time. Wash, rinse, repeat.
Also, another kludge, modify the startup scripts to start daemons in the background, rather than waiting for them to return control to the script on their own. Might squeeze a little bit more time into the startup.