All Sifrei Torah I've seen have lines etched out to ensure that the Sofer writes the letters straight. (I have heard this is a Halacha l'Moshe Misinai - source?) Is this necessary for Mezuzos and Tefillin as well?
This is called שרטוט Sirtut.
A Mezuzah without Sirtut is invalid (ShA YD 288:8).
Tefillin need Sirtut on just the top line (or others say top, bottom and both margins), assuming the Sofer can maintain straight lines throughout even without the Sirtut (ShA OC 32:6).
A Sefer Torah as well as all books of Tanakh need Sirtut (ShA YD 284:1) including a Megillat Esther (ShA OC 691:1).
Even writing three words of a verse on a piece of paper requires Sirtut, though some are lenient in the context of idiomatic usage of quotations or if proper Torah script isn't used (ShA YD 284:2).
Rambam writes (Hilkhot Tefillin 1:12) that a halakha l'moshe misinai dictates that sifrei torah and mezuzot have etchings; sirtut, but that tefillin do not need sirtut.
הלכה למשה מסיניי, שאין כותבין ספר תורה ולא מזוזה, אלא בשרטוט; אבל תפילין, אינן צריכין שרטוט
This is based on the simple reading of Menahot 32b which states that tefillin don't need sirtut and that sirtut for mezuzah is a halakha l'moshe misinai. The source that sirtut for a Torah scroll is also a halakha l'moshe misinai isnt as clear. (Cf. Hagahot Maimoniot there), but it could perhaps be inferred from Megillah 16b, cf. Rashi s.v. kaamitah shel Torah.
Others, most notably Rabbenu Tam (cited by Hagahot Maimoniot: 8), hold that etchings are necessary for tefillin.