How tall would the building need to be? How polluted the air?

About four stories, and as polluted as London.

Parsons Brinckerhoff conducted a study on the effect of the change in air quality with height in London and Cardiff UK, measuring nitrogen dioxide concentration. They found:

The results show that air quality does indeed improve with height (mainly at roadside locations) up to the fourth floor of typical buildings. Beyond this a further reduction is minimal

Exactly what you mean by "a grayscale sky" I am not sure, but London has experienced visible levels of pollution, and it would be expected that this would follow similar patterns.

Roadside NO2 diffusion tube monitoring with height in London and Cardiff. Each green point indicates the average monitored NO2 concentration for each floor and the red error bars indicate the minimum (left) and maximum (right) NO2 concentrations measured at each floor.

How tall would the building need to be? How polluted the air?

About four stories, and as polluted as London.

Parsons Brinckerhoff conducted a study on the effect of the change in air quality with height in London and Cardiff UK, measuring nitrogen dioxide concentration. They found:

The results show that air quality does indeed improve with height (mainly at roadside locations) up to the fourth floor of typical buildings. Beyond this a further reduction is minimal

An example of pollution sufficient to obscure vision would be the Great Smog of 1952. This is substantially thicker than that required to alter the colour of the sky:

Visibility could be down to a metre or so in the daytime. Walking out of doors became a matter of shuffling one's feet to feel for potential obstacles such as road kerbs. This was made even worse at night since each back street lamp at the time was fitted with an incandescent light bulb, which gave no penetrating light onto the pavement for pedestrians to see their feet or even a lamp post.

This was caused by a particular weather event (a temperature inversion) along with pollution, and extended much higher, 100-200 metres deep. One could choose any amount of pollution between these levels as fits the story.

Roadside NO2 diffusion tube monitoring with height in London and Cardiff. Each green point indicates the average monitored NO2 concentration for each floor and the red error bars indicate the minimum (left) and maximum (right) NO2 concentrations measured at each floor.