I don't share your experience that work politics have to be a fact of life, but I've worked at mostly smaller companies (non start ups). I think it's probably harder to form cliques at a smaller company where there's less people and everyone kind of knows each other. Maybe something to consider.