Coming from a server....it can be stressful when one of my customers has such specific requests, but when they let me know right off the bat what they need, it makes things MUCH easier for me. Not only can I suggest to them what to order, but I know things about the menu they might never think of, and I'm much more willing to take the extra step needed to make sure everything is prepared properly. Just make sure you are patient with your server, you're clear with what you want, be nice (servers are PEOPLE, too) and tip accordingly (if you're not sure how to tip, just double the tax!).

I work at Outback Steakhouse (which is AWESOME for me, not only because of the discount, but the food is AMAZING and so much of it fits into the Paleo Diet!) and we are MORE than happy to accommodate specific requests. I'm sure you've heard "No Rules, Just Right" well, we really mean it! We have a separate Gluten Free menu and GF buttons in our POSI computer system (to ensure the cooks know what items are GF).
If you let your server know right off the bat "Just so you know, I'm on a special diet and I can't have dairy" (or even say you're allergic to diary) then they can tell you "Okay then we'll grill your Filet with olive oil, not butter"...which is helpful because I don't think most people know we use butter to grill our steaks.

But yeah....I am very specific when I go out to eat, if I'm ordering Paleo or not! I also tip about 25-30% mostly because of karma :)

If you are going out to eat you pay for the food, the service, the preparation, the table to sit, the utilities, the furniture, and the people to make and serve your food. Because of this by all means order what you want, you are paying for it! The restaurant staff and companions shouldn't be critical of your specifications, you're just asking for what you want. Good for you.

I am no more picky or complicated than any vegan or vegetarian.

LOVE IT! THE MORE OF "US" THERE ARE, THE MORE CHANGE WE WILL MAKE!!!!!

it's also a HUGE help if, when making reservations a day ahead or more, call the restaurant or comment on your Open Table reservation that you have specific dietary needs, and what they happen to be. This is incredibly helpful, as often what happens is someone (management or your pre assigned server) has a chat with the chef and the chef points them towards the best items for your needs or the most "substitutable" dishes.

As a server at largely small neighborhood fine dining restaurants, I didn't have an issue with people with food sensitivities. I was proud I knew what was in our food or could ask the chef. The only people who bugged me were people who ordered trout and then, when it came out whole, about went through the roof and wanted it sent back for the head to be removed by the kitchen. I loved putting that whole animal in front of them. Once a little boy ordered it and his mother was a bit panicked asking for it to be sent back, meanwhile the boy had already lopped off the head, put it on a side plate and requested that his server not take it away because "he liked it there." Oh, the whole staff was so happy about that fish head staying there staring at Mom.

That is great! Don't feel bad - any server and or chef worth their salt will be much happier with you being picky before you order rather than after.

I have found places to be really accommodating with our needs - but we don't go out that often and we choose places that we know will be good about it.

I ordered the "omelet of the day" today BUT please hold the cheese, hold the home fries, hold the toast, substitute yam fries for home fries, and ditch the mystery dipping sauce and house-prepared ketchup. And black coffee. Please. No worries.

It can be a bit of a pill because many items don't even mention that they are coated with this or that substance. I, too, am very fond of eating at home. I know what goes in and on the food, and almost always, it is better tasting, better prepared food. At some point, though, when you have to eat out (like when you are travelling), sometimes you just have to do the best you can and say WTH, it's as good as its gonna get.

You are awesome--my short-term memory gets overloaded way too quickly to pull off an order like that. In fact, in order to avoid having to specialize my orders too much, I only eat out at two restaurants: this family-owned Thai place that subs steamed veggies for rice without blinking, and this awesome BBQ shack (nothing more paleo than a huge pile of ribs and brisket, right?).

Both changing environments and selecting them = paleo smarts (cite: Robert Sternberg).

I've always worked in customer service and been a waitress on and off for 7 years now, so I can't bring myself to be that customer (not that most customers who want full information and have specific dietary needs aren't very nice people, but it makes everyone's job so much harder).

I don't eat out hardly ever these days. My cooking is better 90% of the time anyway. When I do, I really just avoid bread, breading, and anything I know is saturated in vegetable oils. I eat rice, potatoes, and while I'm trying not to make cheese a regular part of meals I will eat it in a pinch. So it's not too difficult to eat on plan.

You sound just like me when I'm ordering.

By the time they have eliminated all the things that I don't wish on my food, there is almost always a bit or a great deal more food of what I DO want... I suspect the chefs don't want the plate looking bare...

or they really do like a customer who knows what he wants!

I don't eat out any more. Too many downsides, but in this economy the biggest one is cost. Why pay twice the price for less than half the meat?

I'm pretty atrocious, too. I love restaurants that let you sub in a side salad for the fries, then I just dump my bunless burger right onto the bed of mixed lettuces and dig in. :)

My fella has never complained about my quirky ordering, but I'm still sorta embarrassed about it. I was so pleased the other day, though, when I found an item I could order directly off the menu. I love French cuisine for that reason! They don't muddle around with silly grains. They'll serve you a hunk of something dead and the veggie on the side, no questions asked, completely standard. :)

I do go that crazy. Typically I'll ask for a salad, no cheese, grilled steak/chicken and ask for oil and a half a lemon. When I order a steak, I'll typically take whatever starch they serve with it unless I've had a starch-heavy week at home. I'll indulge in sauces if I go out, considering I only eat out once every few weeks anyway.

That is exactly what it sounds like when I order but I've found that most places are happy to accommodate, I just make sure I'm nice about it and try to tip well.

I am big on finding local restaurants that cook just the way I want my Paleo meals. I actually interview them to determine how they cook. I've found at most of your family owned and operated joints, that they will cook for you just the way you want it. At the fast food joits, it's more difficult as stuff is pre-made, packaged and cooked.

I once ordered "the chicken wrap without the wrap, please." You would have thought I asked for alien brains! The waiter repeated it back to me, I confirmed, he repeated it again, I confirmed again. On the 3rd repeat, I clarified and said, "I want everything in it, just no tortilla." He still looked confused and I didn't know what would come to the table. Luckily, I managed to have a "wrap with no wrap" for lunch that day.

This ordeal happened during a work lunch outing while I was surrounded by coworkers and a manager. Fairly embarrassing. I didn't realize my request was difficult. Maybe it was just the server?

I usually choose an item based on what I want to eat plus what would be the easiest to order. This is most difficult during lunch as most places around my office are delis/sandwich shops. A salad topped with cold chicken chunks is not very appetizing. That chicken wrap, on the other hand, has warm grilled chicken. Go figure. 8)

I barely eat out (good for my wallet now that I spend more on paleo groceries).

But when I do eat out I'm not strictly paleo. I try to stick to meats and/or vegetables and avoid the dessert menu.

The best thing about paleo is that (at least for me) it removes almost all food compulsions. So I'm not tempted to binge or eat foods that make me feel sick. And not being ravenously hungry, I can go to a restaurant and simply nibble on something.

I think a person should order what he or she wants; however, it is smart to do it very politely and to not even appear to be demeaning in any way. While the posts of "you pay for it, get it how you want it" are correct, you don't really know what goes on back in the kitchen. Just be nice. If something comes on my plate that I am skeptical of, I will generally give it a try. If it tastes good but perhaps toes the Paleo line (e.g. sauteed in a "bad" oil), I might eat it. If it doesn't appeal, I won't eat it but generally won't send it back unless it is the main dish.

I pretty much always eat before going to restaurants, or just fast if I can't get something I consider healthy.

To be honest, I consider it a borderline eating disorder. Although my weight/composition are good enough now that most people that knew me before eating whole foods (etc) leave it alone.

My experience has been that restaurants generally do not even stock olive oil (refined or otherwise) and instead relay on corn and soy based vegetable oils. That said, better restuarants probably dodge around this issue.... but for where I live....