Help with Postgres 9.1 data import (is 4x expected data size, 4x slower than MySQL, and index still needed)
SubQuestion 1: I don't know of any way to get rid of the 23 byte header. There is also a 24 byte header on the page. http://www.postgresql.org/docs/8.3/static/storage-page-layout.html

SubQuestion 2: This guide should help. As suggested, increasing maintenance_work_mem is advised, but also increasing checkpoint_segments should help (to reduce the frequency of checkpoints). You've set your work_mem at 64GB, which seems really high. I would suggest keeping it under 2GB even on a system like yours. work_mem is for doing sorts and operations of that nature. http://www.postgresql.org/docs/current/interactive/populate.html

SubQuestion 3: I am not able to find any information on the physical layout of indexes within the pages. I would create a temporary table, fill it with test data (1 million rows?), create a temporary index, get the size of the index from the system, then divide by the number of rows to get the average. I can't show you an SQLFiddle version because it doesn't allow access to system functions. Try these techniques: http://postgresql.cc/postgres-index-size

PS - 25 billion rows? That's more than I've ever dealt with. I'm in the 4 billion range for one particular table ... For comparison, other database servers, like SQL Server 2008+, have a minimum 9 byte header for each row, so you can't entirely get rid of it but I've always thought that PostgreSQL's 23 byte header was a bit excessive.