I have a sentence that I need to replace; one that is somewhat cliché. What would be a good sentence (Or perhaps a phrase) that could indicate change in a somewhat stale/monotonous environment?
Like a breath of fresh air.
The construction you mention seems like the tail end of a simile. Whenever you say that something was "fresh like a spring rain" or "cold like an arctic wind", you're using a simile (although similes don't need to have the word like in them).
Without seeing the context if the fragment, it's difficult to propose alternatives. I would, however, argue that similes themselves are overused. You can always be direct and say what exactly was changed and why it was welcome; your writing will be far more accurate as a result. Failing that, I suggest writing your own similes, making your writing fresher and more interesting.
In the first place, what you have is not a sentence. It is a sentence fragment, or a phrase, punctuated like a sentence.
That said, you can approach this exercise two ways: either to look for another cliché or to find something original to say. If the former, there are plenty of other clichés you might try, but you would wind up in the same predicament you're in now, so why bother?
If the latter, there are plenty of things you might say.
Really, there are limitless possibilities. Use your imagination and come up with your own. You can't build your writing skills without working on them.
Thank you for your interest in this question.
Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.
Would you like to answer one of these unanswered questions instead?