There are numerous lower-bound results that are related to distributed (and parallel) algorithms. For a partial list, see the surveys from 1989 and 2003.
Here are some further examples: Linial (1992) shows that 3-colouring a cycle requires $\Omega(\log^* n)$ communication rounds (and this is tight). Similar but more general results include, e.g., Czygrinow et al. (2008), which is a neat application of Ramsey's theorem. For something different, see, e.g., Kuhn et al. (2004).
