Automata Theory / Formal Language Thesis Topic
I think David Eppstein is too dismissive of the area of automata theory and formal languages.  The claim that "getting it published in top-level conferences and convincing someone to hire you once you graduate may be problematic" seems to be what Haldane called Aunt Jobiska’s Theorem: "It’s a fact the whole world knows."

In fact, there are good conferences (such as STACS and ICALP) that routinely publish results in automata theory and formal languages; there are well-attended conferences (such as DLT) that focus on the area; it is a very active area in Germany, France, and Italy; there are great open problems in the area; and I know many students that have had no problem getting jobs.