Formation of protrusions and protein segregation on the membrane is of a great importance for the functioning of the living cell. This is most evident in recent experiments that show the effects of the mechanical properties of the surrounding substrate on cell morphology. We propose a mechanism for the formation of membrane protrusions and protein phase separation, which may lay behind this effect. In our model, the fluid cell membrane has a mobile but constant population of proteins with a convex spontaneous curvature. Our basic assumption is that these membrane proteins represent small adhesion complexes, and also include proteins that activate actin polymerization. Such a continuum model couples the membrane and protein dynamics, including cell-substrate adhesion and protrusive actin force. Linear stability analysis shows that sufficiently strong adhesion energy and actin polymerization force can bring about phase separation of the membrane protein and the appearance of protrusions. Specifically, this occurs when the spontaneous curvature and aggregation potential alone (passive system) do not cause phase separation. Finite-size patterns may appear in the regime where the spontaneous curvature energy is a strong factor. Different instability characteristics are calculated for the various regimes, and are compared to various types of observed protrusions and phase separations, both in living cells and in artificial model systems. A number of testable predictions are proposed.