But is there an alternative if you need these hard-to-guess public identifiers? They will always have some randomness and you'll need to index them so it seems unavoidable.
(I understand there'll still be an index for the public key -- the argument would be that you don't bear the cost for that for most queries.)
Create a separate table mapping integers to unique IDs, and join with this. You can generate that in advance, so can avoid gradually building the index.
Your INSERT becomes even more expensive because you have 2 update 2 indexes, and your lookup doesn't change.
I get the benefit if you use the id as a FK or if the database must have data on disk in PK order like MySQL or MSSQL (?). On PostgreSQL if you just insert & read on that key only it seems objectively worse.