Switching to bilinear could make things worse in this case because the data is discrete, even densely discrete. Bilinear resampling is more for continuous data, and even the Improving the display of raster data help page is really geared toward continuous data and not discrete data.
The site must contain metadata describing the coordinate system used. Do you know what it is?
In the layer properties (double click the tiff layer in the ArcMap table of contents), go to the Display tab and change the resampling from Nearest to Bilinear. See "Display resampling" in the ArcGIS Help doc - Improving the display of raster data.
What is the coordinate system of your data frame? Have you tried loading the tiff into a new ArcMap session?