How to find all "nearly roots"?
The following algorithm will solve your problem

Strategy

The task is decomposed into 2 subtasks:


Derive an annotated DAG from $G$.
Contract cycles in $G$ to single nodes while traversing the implied spanning tree of a DFS, creating a graph $G'$, 
Conduct a BFS on $G'$ with reversed edge orientations, identifying and marking nearly roots.


Details


Perform a DFS on $G$. It's used as a tool to identify and contract cycles while keeping tabs on the number of contracted nodes.
For cycle contraction it suffices to detect backward edges ( mark/unmark nodes when entering a node for the first time / leaving it for the last time ). Each time a backward edge $(w, v)$ has been detected, all nodes on the current DFS path $p = v \stackrel{*}{\rightarrow} w$ are coalesced into a new node $v'$, edges from nodes on $p$ are retained. These modifications can be done in situ ( $V_{i} := (V_{i-1} \ \{ x \in V_{i-1} | x \in p \}) \cup \{ v' \}$, $E_{i} := (E_{i-1} \ \{ (x,y) \in E_{i-1} | x \in p \}) \cup \{ (v',y) \in V_{i}^2 | y \notin p \})$ for the $i$-th contraction, starting with $(V_0, E_0) := (E, V)$). Mark each node in $V_{i}$ with an attribute represents containing the number of nodes from $V$ it represents (i.e. initialising this attribute with $1$ and adding the cycle length subtracted by $1$ for each contraction). in case of contracted nodes also record the represented nodes by adding it to a stack attribute. 
The resulting graph $G'$ is cycle-free (in particular: irreflexive). Next perform a BFS on $G'$ with all edges reversed. Propagate an attribute reachable: $V \rightarrow \mathbb{N}$ along the way which locally computes as $\text{reachable}(v) := (\text{represents}(v) - 1) +  \sum_{w \in pred(v)\subset V'} \text{reachable}(w)$ with pred denoting the set of predecessors  and reachable being initialised to $0$ for all maximal elements in $G'$. for all nodes $v \in G'$ with $\text{reachable}(v) \geq |V|/2$, mark all represented nodes from the original graph $G$ as nearly roots.


Complexity


Complexity of this operation is $O(E)$, as each edge is traversed at max 2 times in the course of the DFS and the contraction while the bookkeeping operations are $O(V)$ in total.
Complexity of this operation is $O(E)$, as each edge in $G'$ is traversed once during the BFS and $|E'| \leq |E|$. Updating reachable is $O(V')$ while marking the nodes from $G$ as nearly roots costs at most $O(V)$.