If I had to choose one, it would be no grains (and therefore no gluten). The damage they can do to the gut opens up doors for all other types of ailments and auto-immune issues.

Closely followed by processed food and sugar. However by cutting all grains you will instantly cut most processed food. By cutting sugar you will avoid the rest.

I agree, but would add in the top 3 no refined industrial oils (canola, etc.)

Without a doubt, ELIMINATE GRAINS.

That makes a bigger difference by far than anything else.

No sugar and strictly no grains at least initially will kick you off and get you in the right mindset. This may radically change what you eat throughout the day and will cause you to change the way you think about food, and you should immediately start to realize the benefits of the diet. It is also a simple rule to follow. Simply cutting out all sugar can have a radical effect on your diet.

I also think that it is easier to just go to the diet "whole hog" (as it were) rather than try to continue to eat the same foods but in some modified Paleo way (i.e. gluten free pasta, faux pizza, etc). Just start eating primarily meats, eggs, and vegetables.

I personally think that many people can be flexible on dairy, a long as you don't have specific issues with lactose or need a very low carb diet, and as long as you're eating only full fat dairy.

It is helpful to have a "crutch" food initially, something familiar that you can go to in a pinch that is "Paleo enough" and satisfying. This might be something like hard cheese or nuts. Just make sure it isn't sugar or grain based.

Cutting out grains is #1, in my opinion. At the same time, filling your fridge and your face with meats and veggies is key. You'll do much better transitioning when you focus on what you CAN eat. And if you don't have the good stuff around, you're setting yourself up to be kinda screwed.. And seriously, STUFF your face so you won't feel hungry for grains. :)

i like this list: http://www.archevore.com/get-started/

but personally, i cut gluten grains first, and still feel like that has had most significant effect on my health. fwiw cutting out sugar (i found out too late) makes everything else much easier!

Agree with the others, though I would lump sugar and grains together. But I'm not gluten intolerant which can really change priorities for some people.

For me it was cutting anything with carbs that made the difference - and it's particularly tough to do it half way, since carbs from one source (say, grains) will trigger an addictive response to consume the other (say, sugar) and visa versa. I even cut fruit in the beginning (I was a big dried fruit addict), but I've lately added melon and berries back in once in a while.

Nothing processed.

Eliminates almost all grain, sugar, veg oil in one fell swoop.