I generally CTRL-N till I get a tile with at least 4 production and 2 essence - and I've since created a modified version of elementaldefs.xml to make it easier.
Unless I can find a 3 essence tile, then I'll settle for 3 production... maybe.
Regardless of food, that 4 production and 2 essence will be the heart of my empire as a fortress.
Production is key in general, especially when the war machine starts - high production both gets you to war footing quicker by building all the base buildings and then producing troops when you're at the desired level of infrastructure.
High essence provides those killer buffs for troops once you're rolling them out - +3 initiative, +3 attack, +3 hit points per unit if you have air, fire, life. +defense is ok, but quite as significant. (I usually take enchanters for scrying pool, so can get +3 or occasionally +4)
My next depends on the essence, if 2+ it will be a conclave (just because I probably haven't reached my food limit quite yet)
Then I'll try to get a town.
I'll try to have 2 or 3 conclaves and 3 or 4 towns and 1 primary fortress. Conclaves to provide the extra research. Towns to provide gold and more importantly faction food.
With all that said, it depends on the situation though.