Based on the following snippet from https://en.wikipedia.org/wiki/Quotient_group:
In a quotient of a group, the equivalence class of the identity element is always a normal subgroup of the original group, and the other equivalence classes are precisely the cosets of that normal subgroup.
It seems that you can simply set $H$ to be the identity element of $G/H$ (taking O(1) time), and then for each element $g \in G$ that has not yet been assigned to any coset, calculate the (say, left) coset of $H$ w.r.t. $g$ explicitly: $\{gh : h \in H\}$, and assign all such elements $gh$ (not just the $g$ we started with) to this coset. Calculating the coset for a particular $g$ takes $O(|H|)$ time, but the entire second phase takes only $O(n)$ time overall, since we only consider elements $g \in G$ that have not yet been assigned to a coset -- this is allowed because (according to that page) the cosets form an equivalence class, meaning no element can appear in two different cosets.