The story of how the first complex nucleated cell (eukaryote) arose is a fascinating one – see Nick Lane’s Power, Sex, Suicide: Mitochondria and the Meaning of life. An article related to this has now appeared in New Scientist.
This describes the discovery of an archaeon (an organism that looks like a bacterium although it is really quite different) in deep water off the coast of Japan. It lives in association with at least one and probably two other kinds of microbe. The crucial event in eukaryote generation is thought to have been the swallowing of a bacterium by an archaeon, and the scenario described in the article looks like the kind of situation where this might occur. However, that doesn’t answer the really important question: was this a one-0ff extremely unlikely event or something that was more or less bound to happen sooner or later?
Given the fact that it eukaryotes appear only comparatively recently in the course of evolution, it still looks likely that it was a lucky fluke, in which case there is probably plenty of life in the universe but almost all of it is at the microbial level of complexity.