Dithering Index Textures?

I have a 8 bit index texture wich I render without interpolation to make sure, I can access the correct indices for my lookup table in the shader. On the texture, there are lines and polygons drawn. So far, so good. Now, I wonder, how to improve this by interpolation or multisampling.
I tried to switch to GL_NEAREST and calculate the color-index by casting the found value+0.5 to integer and use the decimal place for transparency, but the results are not great, especially, if areas with different color indices touch each other.
Is there a proven, good solution to do it better? Or must I switch to Supersampling altogether?