Meh. I'm just openly and clearly one of those people with special food needs, and I refuse to be embarrassed about it (but I'm also not rude about it--I simply make sure to plan ahead). I've been living the celiac life for about six years now, so I'm pretty okay with just telling people outright what I can and can't have, ordering very specifically when I eat out, and making sure I always have something I can eat tucked into my purse or in my car on roadtrips. I make sure I tell the travel agent when I book my flight that I need a celiac meal, and I put food I can eat into my carry-on just in case. I stop at grocery stores and buy food I know is safe when I'm on the road, and I put a cooler in the back of my car for long trips. I've also learned which restaurants are good at accommodating and which ones to just avoid.
If you were diabetic and couldn't have sugar, I'm assuming you'd be quite clear about it with people. Being celiac is no different, and it's important to your health to put your dietary needs ahead of your sense that you shouldn't make a fuss or be a bother.
Also, in my priority list, eating gluten-free is more vital than eating primal-ish in any other way. I'll take a vegetarian chickpea curry that I know is gluten-free over a steak with questionable seasonings any day. Chickpeas might not be ideal, but they're not going to cause me immediate GI troubles, stomach pain, joint pain, and a dermatitis herpetiformis outbreak.