If you want to truly minimize the size of the package, the best way to do it is to
- physically build a prototype, and
- use a power meter to measure the consumption under worst-case* conditions.
*This will be a function of whatever hardware you're using and (perhaps more importantly) the computational load. You'll have to find out how much load your software suite will put on the system and ensure that your test suite meets or exceeds this load.
I would add a 50% derating factor to your measurement to account for unexpected things - you don't want your embedded system browning out after doing a software update, for instance. This also will improve the life of the power supply (less power = less heat = longer life).
Desktop PC power supplies are generally ATX-compliant, which imposes certain specification criteria on the manufacturers (regulation, overload, etc.). Desktops are inherently (dare I say infinitely) configurable, and because of this it's difficult to say how much power a typical end user will need - hence, large-ish power supplies (hundreds of watts up to a kilowatt, and beyond). Too much power capability is never a problem - too little, well, that's a totally different issue.
You are correct in that the 12V rail is generally for peripherals (hard drives, optical drives, etc.) and the lower power rails are for the 'guts' (5V as housekeeping, 3.3V to feed VRM modules to power the processor).
If your mobo is expecting multiple rails, you're obligated to provide them. If the mobo could convert 12 down to 5 and 3.3 (which often happens on laptop computers, BTW) then the power supply manufacturers wouldn't bother providing those rails and you'd only need a single rail.