Okay, I think I got it really figured out. Symbols and numbers will be atomic. Everything else is a tree: strings will be a list of symbols.
I'll have gensyms too, which are atomic like symbols, but are unique. It would be possible to build gensyms using just numbers + trees, but I think it's more consistent to make them atomic, since they're a kind of symbol.
Types then will be actual genuine gensyms, rather than almost-gensyms.