Writing a select statement to return the results in order sounds tricky [I think the top-level post mentions this]. Even doing it in the application code would give me pause for thought.

It's a recursive query, but it's basically the simplest recursive query. It's not that bad.

  WITH recursive_traversal(depth, id)
  AS (
    -- base case: the root has no previous
    SELECT 0, id
    FROM todo
    WHERE previous IS NULL
      AND user_id = $1
  
    UNION ALL

    -- recursive case: traverse to next row
    SELECT depth + 1, todo.id
    FROM todo
    JOIN recursive_traversal r ON r.next = todo.id
    WHERE depth < $2
  )
  -- we only accumulated the ids, so join one more time to get the rest of the columns
  SELECT todo.*
  FROM todo
  JOIN recursive_traversal USING (id);

You're right, it's not that bad! I'm going to study recursive queries, seems like they can be really helpful for some things.