Here is one way in which you could approach it: On the Lisp side, you can just let people define tables in any order, since non-existant foreign targets aren't a problem there. When creating a whole 'database schema' at once in the database, just create the tables first, and then the keys, and let any errors generated by non-existant tables go through. When creating or resetting a single table, if it has any foreign keys into tables that do not exist, check whether such a table is defined on the Lisp side -- if it is, raise an exception with a 'create this table' restart, otherwise, raise an unrecoverable exception.
(This might, of course, have some problems that I haven't thought of yet, but I think it would be workable.)
Will submarine also have possibilities to define sequences, stored procs, and views? It would be cool to have a single place to define whole db schemas in Lisp, and then have convenient ways to create them all at once in an actual database. -- And of course, the hypothetical 'automatically detect differences between the schema defined in Lisp and the one existing in the database and interactively update the database' functionality might also be something you can think about -- if Jaap allows you to waste another two months on this, hah.
Cheers, Marijn