How should I deal with horizons?
Unfortunately I don't have enough points to make this a comment, but the answer to this question is entirely subjective. "Tacky" "flat" and "look nice" could mean many different things to different people.
A visual reference to what you've tried that's not working and a hint of what it is that you're trying to accomplish would be a better starting point...

Some suggestions: It does help to have some atmospheric fog. Objects close to the camera should be sharper than those far away. You're always looking at the horizon through the humidity and other particles in the air, therfore count on some distortion caused by refraction or dispersion. In a landscape think of the horizon line as the brightest value, and make it fall at a strong point in your composition.
The horizon is so very far away, use the depth of field to blur it and bring the elements in the foreground in focus.
The sky is never as single color, but a subtle canvas of different tonalities. Use gradients and textures on it too.
You should look into the the vast history of painting (the subject has been dealt with since the renaissance).
Pick up a book or two on perspective and composition. There's been rivers of ink written about this...