The scaling on zoom thing is one of the reasons I'm thinking about making a 3D tileset. While it wont help so much with tiny, zoomed out tiles being hard to distinguish, it should mean any mid-large tile size will look nice without having to make multiple versions of every tile.
Maybe you could just take more detailed control over filtering? That's one of the big advantages of shaders in 2D graphics IMO - you're not locked into bilinear scaling. You can actually control which mipmap your shader samples if you like - use the textureLod() function instead of texture().
Signed distance maps are popular for "vector"-looking graphics, for example, and there are tools available to make them from high-res black-and-white images. Maybe you could use an SDM for a really nice smooth outline, and add a low- or mid-res bilinear-filtered color map?
That would require some way to provide additional texture inputs to the pixel shader beyond the current color/alpha tile maps. Baughn, have you thought about that at all? I know you're making a bunch of changes to the texture atlasing...
Multiple inputs would also allow foreground color masking, which I think people have mentioned here before. And personally, I'd be excited about the possibilities that would be opened up by adding depth maps to the tiles.