How do Titania's Song and Mycosynth Lattice interact? What happens if Song enters the battlefield first, Lattice enters first, or they enter at the same time? Is there any circumstances under which all the lands would turn into 0/0s and die?
Here is my current understanding, based on the Gatherer rulings for Opalescence
This is the current interaction between Humility and Opalescence: The type-changing effect applies at layer 4, but the rest happens in the applicable layers. The rest of it will apply even if the permanent loses its ability before it’s finished applying. So if Opalescence, Humility, and Worship are on the battlefield and Opalescence entered the battlefield before Humility, the following is true: Layer 4: Humility and Worship each become creatures that are still enchantments. (Opalescence). Layer 6: Humility and Worship each lose their abilities. (Humility) Layer 7b: Humility becomes 4/4 and Worship becomes 4/4. (Opalescence). Humility becomes 1/1 and Worship becomes 1/1 (Humility). But if Humility entered the battlefield before Opalescence, the following is true: Layer 4: Humility and Worship each become creatures that are still enchantments (Opalescence). Layer 6: Humility and Worship each lose their abilities (Humility). Layer 7b: Humility becomes 1/1 and Worship becomes 1/1 (Humility). Humility becomes 4/4 and Worship becomes 4/4 (Opalescence).
According to this ruling, the fact that Titania's Song removes abilities from artifacts is irrelevant. The continuous effects still happen.
So starting with layer 4, we have Mycosynth Lattice turning things into artifacts and Titania's Song turning things into creatures. Since Song has a dependency on Lattice (because it changes the set of things that Song effects), Lattice is always applied first regardless of timestamps. So they're both artifacts, and then become artifact creatures in layer 4.
In layer 6, they both lose all abilities
In layer 7, they become a 4/4 and 6/6 respectively, despite the fact that they lost their abilities in a previous layer.
All lands will turn into 0/0s and die, regardless of timestamps.
This seems like a weird result, but it's the best I can determine based on the rulings I've seen.
The multiple type-changing effects involved here is similar to a popular combo that uses Mycosynth Lattice and March of the Machines. (Titania's Song is slightly different in that it removes non-creature artifact's abilities as well, which is interesting but doesn't ultimately change the way the continuous effects of these static abilities are applied.)
Both cards create continuous effects, which are more specifically type-changing effects. Continuous effects are applied in layer order according to rule 613.1
613.1. The values of an object’s characteristics are determined by starting with the actual object. For a card, that means the values of the characteristics printed on that card. For a token or a copy of a spell or card, that means the values of the characteristics defined by the effect that created it. Then all applicable continuous effects are applied in a series of layers in the following order:
613.1a Layer 1: Copy effects are applied. See rule 706, “Copying Objects.”
613.1b Layer 2: Control-changing effects are applied.
613.1c Layer 3: Text-changing effects are applied. See rule 612, “Text-Changing Effects.”
613.1d Layer 4: Type-changing effects are applied. These include effects that change an object’s card type, subtype, and/or supertype.
613.1e Layer 5: Color-changing effects are applied.
613.1f Layer 6: Ability-adding effects, ability-removing effects, and effects that say an object can’t have an ability are applied.
613.1g Layer 7: Power- and/or toughness-changing effects are applied.
This is performed whenever state-based actions are checked. The relevant layers here are layer 4 and layer 7.
Since Titania's Song depends on Mycosynth Lattice's effect, the timestamp rule is overridden.
613.7. Within a layer or sublayer, determining which order effects are applied in is sometimes done using a dependency system. If a dependency exists, it will override the timestamp system.
613.7a An effect is said to “depend on” another if (a) it’s applied in the same layer (and, if applicable, sublayer) as the other effect (see rules 613.1 and 613.3); (b) applying the other would change the text or the existence of the first effect, what it applies to, or what it does to any of the things it applies to; and (c) neither effect is from a characteristic-defining ability or both effects are from characteristic-defining abilities. Otherwise, the effect is considered to be independent of the other effect.
At layer 4, Titania's Song must wait to for its dependencies to be applied before it can be applied. Mycosynth Lattice gives all permanents the artifact type. Then Titania's Song can be applied, changing non-creature artifacts into creatures. At layer 7, all artifacts that were turned into creatures from Titania's Song have base power/toughness equal to their converted mana cost.
The layers have been applied, which leaves us with 0/0 creatures.
The next time a player would get priority (which is probably immediately afterwards), we check state-based actions.
704.3. Whenever a player would get priority (see rule 117, “Timing and Priority”), the game checks for any of the listed conditions for state-based actions, then performs all applicable state-based actions simultaneously as a single event. [...]
One relevant effect of this state-based action check is that any creatures with toughness of 0 (any previously non-creature artifact with converted mana cost 0) are put into the graveyard. This might include lands, since they are now creatures as well. (Though if something buffs the toughness of creatures, it could increase their toughness above 0 and save them from dying.)
Note that if a permanent was already a creature, its power and toughness won't be based on it's converted mana cost. For instance, if Liege of the Tangle turned your lands into creatures prior to this, they will still be 8/8.