Task Dependencies (different meaning of "dependency" from other suggestions)
Being able to associate tasks with other tasks (in terms of, "This task starting is dependent on this other task ending") would be extremely helpful, and is the most useful feature I can currently think of adding to Todoist.
I currently crudely account for this by assigning a "wf" (waiting for) tag to tasks waiting for other tasks, but it requires a lot of manual effort, is dumb (in terms of, the task doesn't know what other task it's waiting on; I have to add it with notes) and is a pretty inefficient use of time.
One task could have quite a number of disparate tasks, across projects, linked as dependencies. It is currently pretty difficult to mirror this real-world, regular occurrence in Todoist, so a solution along these lines would be great.
In terms of practically how this could be implemented, I would think the UI could be similar to the one found in the Android (and likely iPhone?) app for associating labels with a given task.
Finally, on a quasi-related note, I really really realllllllly hope that the Todoist web team makes the UI for label assignment similar to the one found in the Android app -- it's so sleek and easy to use; I love it!