Why doesn't greedy work for Clique?
Consider the graph consisting of a clique on $n/3$ vertices and a complete bipartite graph with $n/3$ vertices on either side. The degree of each vertex in the clique is $n/3-1$, whereas every vertex in the bipartite graph has degree $n/3$. Your algorithm would thus remove all the vertices in the clique. The remaining graph is bipartite, and so its maximal clique contains only two vertices.

So your algorithm finds a clique of size two instead of a clique of size $n/3$.