Your two examples are both correct.
New York is the most beautiful city = There is unspoken information here (in fact I would go so far as to say that this is not a naturally complete sentence). NY is the most beautiful city [in America]/[in the world]. Here, "most beautiful" describes both "New York" and "the city".
New York is most beautiful in winter = Here "most beautiful" describes "New York" at a particular time of year. It is effectively "New York is at its most beautiful in winter".
If you imagine that the two statements are the answers to questions:
1) What is the most beautiful city [in the world]?
2) When is New York at its most beautiful?
I'm sure you would know that the article is to be used/omitted respectively in those two questions. The statements follow the same pattern.