Fast Computation of First k Eigenvectors of Graph Laplacian
Answer to Q1:

In [1], it is argued at the end of section 1 that the first k eigenvectors can be approximated in time roughly $O(mk)$ (up to log-factors), with $m$ the number of edges. They are not very precise in their statement however, but I'm not aware of a better reference explictly stating this.

Answer to Q2:

No, this will not hold in general. You are describing a $k$-dimensional embedding of the nodes $[n] \to \mathbb{R}^k; i \mapsto U_{i,1:k}$, as is used in for instance spectral clustering. For nodes $i, j$ which lie in the same cluster (e.g., in the same clique of a dumbbell graph), the quantity $\|U_{i,1:k} - U_{j,1:k}\|_2$ will be small for sufficiently small $k$. On the other hand, if $i \neq j$ then $U_{i,:}$ is orthogonal to $U_{j,:}$ and hence $\|U_{i,:}-U_{j,:}\| = \sqrt{2}$.

[1] Koutis et al. "Faster spectral sparsification and numerical algorithms for sdd matrices." (2015)