When I started playing I actually jumped straight from Chieftain to Noble by mistake, and I didn't actually think even that was that big an increment in difficulty. I went from easily winning each game to getting beaten at the finish line in each game. When I found out I had accidentally skipped a difficulty it only took me a couple of practice games at Warlord to successfully win every Noble game too.
I don't know specifically what made Noble come so natural to me, but I have this theory:
At lower difficulty levels one can succeed with monotone and repetitive strategies, doing things excactly the same every game, and focusing exclusively on certain aspects of the game. The "threshold" for such strategies seems to lay between Warlord and Noble. I believe it was such habits that made me a mediocre CivIII-player, and when I had to "relearn" Civ with IV anyway, I tried to be adaptive in my strategies from the very beginning.
One specific thing that does come to mind, and has already been pointed out by previous posters, is that it is paramount to keep an adequat sized military throughout the game, even for builder-style players. This will help keep the more reasonable AIs off your back, and let you defend yourself when the aggressive ones attack. At least this is what seemed to make the difference for me.