I second everything what Jerome wrote. With additional few notes:
1. most important thing is to spread nodes over lot of parent nodes. We had lot of bad experience with importing thousands of objects under same node as single publish is a bit slower with every new sibling. I didn't have time to investigate why is that, maybe it can be avoided somehow...
2. to reduce single publish try to hack temporary "publish" operation definition in kernel/content/operation_defintion.php and remove every method that is not crucial, like:
post_publish, remove-temporary-drafts, create-notification, register-search-object, generate-object-view-cache, clear-object-view-cache, pre_publish. Maybe even some others. You need to know exactly what you are doing, of course. Try different hacks with couple of thousands and measure the single average publish time....
Aditionaly, it could be lucrative performance wise to hack out some features (e.g. browserecent, etc), but generally I think those should be possible to disable through ini settings.