I hate having to up the dificulty to make a game more interesting - because usually that just means the enemy shoots straighter and for more damage, and you get less cash etc.. I can't even think of any games where the puzzles become harder if you increase the difficulty.
That said, I usually start a game on whatever is 1 level above normal, be it veteran, Chieftain or hard or whatever. Seems that usually keeps me on my toes.