OK, so for fixed dimension d, assuming the resulting polytope to be simplicial (with prob 1) is indeed crucial for the algorithms to run in linear time?

This is not what I said. Note that in the expression O(mnd) the parameter m (number of facets) depends on n (number of vertices/input points). Roughly speaking, m lies in \Theta(n^(d/2)) by the upper bound theorem. The complexity O(mnd) is attained, e.g., by reverse search of Avis and Fukuda (1991).

In fixed dimension and for points on the unit sphere, m is bounded by a linear function in n (see Borgwardt 1987).

At any rate, computing the vertex facet incidences takes O(mnd) time (by checking mn scalar products in R^d, if both the vertices and the facets are known; no other conditions on the polytope), and there is no way to make this faster.

All complexity statements refer to the unit cost model.