We provide bounds on the smallest eigenvalue of grounded Laplacian matrices (which are obtained by removing certain rows and columns of the Laplacian matrix of a given graph). The gap between our upper and lower bounds depends on the ratio of the smallest and largest components of the eigen-vector corresponding to the smallest eigenvalue of the grounded Laplacian. We provide a graph-theoretic bound on this ratio, and subsequently obtain a tight characterization of the smallest eigenvalue for certain classes of graphs. Specifically, for weighted Erdos-Renyi random graphs, we show that when a (sufficiently small) set S of rows and columns is removed from the Laplacian, and the probability p of adding an edge is sufficiently large, the smallest eigenvalue of the grounded Laplacian asymptotically almost surely approaches mu(w)vertical bar S vertical bar p, where mu(w) is the mean edge weight. We also show that for weighted random d-regular graphs with a single row and column removed, the smallest eigenvalue is Theta(1/n), where n is the number of nodes in the network. Our bounds have applications to the study of the convergence rate in consensus dynamics with stubborn or leader nodes.