It really depends on the game your playing. I would argue that an environment could have average composition and art but still be the best thing since sliced bread. You ask the question of what makes a great game environment, but seem to focus on it as an artistic question. Art will play a key roll in the success of a game…
What makes you go wow is when every design principle is sound and it's working together really well with all the other departments but that's a thing that's really hard to get. There is no magic sauce solution to these things so you shouldn't expect an answer that will solve all problems. Usually Environment Art for games…