There are techniques beyond color, contrast, and detail to make thing appear distant. In the example below, from The Machine by Nifflas, there are at least 4 tricks.
- Layers: The small trees appear distant because they are behind foreground objects.
- Size: The small trees appear distant because they are smaller than the middle tree.
- Fog: The small trees appear distant because a subtle fog fades them out at the bottom.
- Semi-Transparency: The dark hills appear distant because the gradient shows through them.
I think making your background tiles semi-transparent might help. Try opacity around 50 to 80%, then try it out with different gradients. This method also helps make tilesets more versatile. Your bright backgrounds wouldn't work very well for a night scene. But, if a dark gradient shows through then they will look darker.