While you might see some improvement by clustering, it's not going to give you what you're looking for by itself. In fact, since you're pulling a single row at a time, I doubt it will do anything, except for reports.
You will get better improvement by moving one of the tables to a second physical disk.
Unfortunately, Postgres doesn't seem to support it, but something like Informix's FRAGMENT BY, or SQL Server's DPV's would give you rocking performance. Alas, maybe next year.