Uma coisa importante ao se tratar a imagem, é a fonte, ou seja, a imagem escolhida para tratar, quanto melhor a fonte em termos de qualidade fotográfica, provavelmente melhores serão os resultados e possibilidades. Contudo, é possível sim tratar e melhorar significativamente imagens de qualidade não tão boas.
A foto que usarei neste exemplo foi tirada por mim mesmo, em Guarapari-ES, em um dia nublado, com a câmera de 3.2MPx do celular Nokia N73 em um dia nublado. É uma foto comum, do dia-a-dia, nada de fotos profissionais onde ficamos fazendo e refazendo poses e fotos até conseguir um resultado bom na própria fotografia.
A imagem original é está aqui:

Para começar, vamos trabalhar com o efeito "Sharpen / Unsharp Mask", utilizando-o para melhorar a nitidez e "profundidade" da imagem.

Em seguida, fazemos um ajuste de "Levels" para nivelar a iluminação da imagem, cortando a área do gráfico que está no piso, conforme screenshot abaixo:

Em muitos casos, utilizo o "Selective Color" para ajustar tonalidades das cores individualmente, portanto, nesta imagem, utilizei somente para retirar um pouco da tonalidade avermelhada do "lodo" das rochas.

Para dar um colorido mais vivo à foto, utilizamos o ajuste de "Hue/Saturation".

Agora vamos começar a ajustar as regiões especificas da imagem, através do modo "Quick Mask" selecione todo o mar e áreas contendo água na pedra, utilize um pincel com dureza mínima, e busque utilizar pincéis de tamanhos diferentes e intensidades de coloração - na escala de cinza - sutilmente diferentes, para conseguirmos uma seleção não tão linear.

Volte ao modo padrão, selecione o inverso, e aplique um "Feather" para suavizar a transição da seleção.

Vamos utilizar o ajuste "Color Balance" para "azularmos" o oceano.

Agora vamos trabalhar com o céu. Entre no modo "Quick Mask" e utilize o efeito "Render / Clouds", volte ao modo padrão e através da ferramentas de seleção como o laço, subtraia da seleção toda a área que não seja o "céu".

Também através do ajuste "Color Balance" ajuste a tonalidade do céu, lembrando sempre de ajustar em todos os níveis de iluminação - Shadows, Midtones e Highlights.
Vamos agora, através do modo "Quick Mask", selecionar somente a modelo para melhorarmos sua iluminação individual.

Voltamos ao modo padrão, selecionamos o inverso e trabalhamos com o ajuste de "Brightness/Contrast".

Agora, duplicamos a camada da foto e aplicamos na nova camada o ajuste de "Levels" conforme abaixo.

Através do controle de opacidade da camada duplicada, mesclamos as duas camadas para finalizar o trabalho.
A fotos antes:

A foto depois:

PS: Todos os ajustes e nomes de menus utilizados são do Photoshop CS3, podendo variar um pouco de versão para versão.